Yoram Moses

TCS Journal 2018 Journal Article

Mutual exclusion as a matter of priority

• Yoram Moses
• Katia Patkin

A new approach to the study and analysis of Mutual Exclusion (ME) algorithms is presented, based on identifying the priority relation that the ME algorithm constructs. It is argued that by analyzing how a process detects that it has priority over all other processes, ME algorithms can be better understood and improved. The approach is illustrated by applying it to Lamport's celebrated Bakery algorithm in the safe register SWMR model. By analyzing how Bakery established and detects priority, cases in which the Bakery algorithm causes processes to block unnecessarily are identified. Namely, a process that already knows that it has priority over another process is made to perform reads and wait on registers of the other process. An optimized version of the Bakery algorithm, called Boulangerie, is proposed, and is shown to be free of any unnecessary blocking. A second contribution of the approach is obtaining a clear explanation for how the Bakery algorithm uses reads from safe registers to detect that a process has priority. Our analysis provides more insight into the workings of the Bakery algorithm than is obtained by other proofs of its correctness.

TARK Conference 2015 Conference Paper

Relating Knowledge and Coordinated Action: The Knowledge of Preconditions Principle

• Yoram Moses

The Knowledge of Preconditions principle (KoP) is proposed as a widely applicable connection between knowledge and action in multi-agent systems. Roughly speaking, it asserts that if some condition is a necessary condition for performing a given action A, then knowing that this condition holds is also a necessary condition for performing A. Since the specifications of tasks often involve necessary conditions for actions, the KoP principle shows that such specifications induce knowledge preconditions for the actions. Distributed protocols or multi-agent plans that satisfy the specifications must ensure that this knowledge be attained, and that it is detected by the agents as a condition for action. The knowledge of preconditions principle is formalised in the runs and systems framework, and is proven to hold in a wide class of settings. Well-known connections between knowledge and coordinated action are extended and shown to derive directly from the KoP principle: a "common knowledge of preconditions" principle is established showing that common knowledge is a necessary condition for performing simultaneous actions, and a "nested knowledge of preconditions" principle is proven, showing that coordinating actions to be performed in linear temporal order requires a corresponding form of nested knowledge.

TARK Conference 2013 Conference Paper

The Shape of Reactive Coordination Tasks

• Ido Ben-Zvi
• Yoram Moses

1. This paper studies the interaction between knowledge, time and coordination in systems in which timing information is available. Necessary conditions are given for the causal structure in coordination problems consisting of orchestrating a set of actions in a manner that satisfies a variety of temporal ordering assumptions. Results are obtained in two main steps: A specification of coordination is shown to require epistemic properties, and the causal structure required to obtain these properties is characterised via “knowledge gain” theorems. A new causal structure called a centibroom structure is presented, generalising previous causal structures for this model. It is shown to capture coordination tasks in which a sequence of clusters of events is performed in linear order, while within each cluster all actions must take place simultaneously. This form of coordination is shown to require the agents to gain a nested common knowledge of particular facts, which in turn requires a centibroom. Altogether, the results presented provide a broad view of the causal shape underlying partially ordered coordinated actions. This, in turn, provides insight into and can enable the design of efficient solutions to the coordination tasks in question. Coordinated action in distributed and multi-agent systems is closely related to knowledge and epistemic states. As a particular example, linearly ordered actions require nested knowledge. Namely, suppose that the occurrence of event e is guaranteed to trigger a response by each of the agents 1, 2, and 3, and, moreover, they must act in this order: first 1, then 2, and finally 3. Then, in a precise sense, K3 K2 K1 occ(e) (which we read as “agent 3 knows that 2 knows that 1 knows that e has occurred”) must hold when agent 3 acts [3]. This generalises from three agents to any finite number. In the theory of distributed systems, asynchronous systems, in which agents have no clock and no timing information is available, receive a great deal of attention [1, 17]. In such systems, Chandy and Misra’s celebrated Knowledge Gain theorem [7] captures the necessary condition for attaining nested knowledge of this form. Roughly speaking, it implies the following. Suppose that a spontaneous event e takes place at agent 0’s site in an asynchronous system. Then K3 K2 K1 occ(e) can hold only after a message chain is formed, that starts from agent 0 after e occurs, and passes through 1 and then through 2 to agent 3. (The message chain may pass through other sites as well; but it must visit these agents in the specified order.) As a result, the only way to coordinate a linearly ordered response to the event e in an asynchronous system is via such a message chain. This theorem captures the shape of the causal structure that underlies linear coordination.

TARK Conference 2013 Conference Paper

Timely Common Knowledge

• Yannai A. Gonczarowski
• Yoram Moses

linear temporal order requires the agents to obtain appropriate nested knowledge (knowledge about knowledge) [5], while coordinating simultaneous actions requires attaining common knowledge of particular facts [17]. The latter connection has found uses in the analysis of distributed protocols (see, e. g. [17, 11, 28]). One of the contributions of [17] was in relating approximations of simultaneous coordination to weaker variants of common knowledge, called epsilon-common knowledge and eventual common knowledge. While common knowledge is typically defined and thought of as an infinite conjunction of nested knowledge formulae, it may also be defined as a fixed point [3, 8]. The variants of common knowledge defined by Halpern and Moses in [17] are most naturally obtained by appropriately modifying the fixed-point definition of common knowledge. All of the forms of coordination analyzed in [17] are symmetric in nature, in the sense that they are invariant under renaming of agents. For example, ε-common knowledge arises when the agents are guaranteed to act at most ε time units apart. In many natural situations, however, asymmetric forms of coordination arise. Let us consider an example. Coordinating activities at different sites of a multi-agent system typically imposes epistemic constraints on the participants. Specifying explicit bounds on the relative times at which actions are performed induces combined temporal and epistemic constraints on when agents can perform their actions. This paper characterises the interactive epistemic state that arises when actions must meet particular temporal constraints. The new state, called timely common knowledge, generalizes common knowledge, as well as other variants of common knowledge. While known variants of common knowledge are defined in terms of a fixed point of an epistemic formula, timely common knowledge is defined in terms of a vectorial fixed point of temporal-epistemic formulae. A general class of coordination tasks with timing constraints is defined, and timely common knowledge is used to characterise both solvability and optimal solutions of such tasks. Moreover, it is shown that under natural conditions, timely common knowledge is equivalent to an infinite conjunction of temporal-epistemic formulae, in analogy to the popular definition of common knowledge. Example 1. 1 (Robotic Car Wash). In an automated robotic car-wash enterprise, there are two washing robots L and R, (with L fitted to soap & rinse the left sides of cars, and R fitted to soap & rinse the right sides), and one drying robot, denoted D. At some point after a car enters, it must be soaped & rinsed from both sides, and then dried. The robot L is a new model, which takes only 4 minutes to perform its duty, while R is an older model, requiring 6 minutes. The drying is applied to the whole car, and it must commence only after washing of both sides is complete. Moreover, drying should not begin more than 5 minutes after the first of the washing robots finishes rinsing the car, as water stains might otherwise incur. It follows that, in particular, no more than 5 minutes may elapse between the time at which the rinsing of the car’s left side ends and the time at which the rinsing of its right side ends. This, in turn, implies that L must start washing the car no later than 7 minutes after — and no more than 3 minutes before — R starts washing it. Finally, it is obviously desirable to minimize the time that the car spends in the Car Wash.

I&C Journal 2012 Journal Article

No double discount: Condition-based simultaneity yields limited gain

• Yoram Moses
• Michel Raynal

We consider the consensus problem in synchronous message-passing distributed systems. A celebrated result states that every protocol that is guaranteed to tolerate up to t crash failures has a worst-case execution in which some process does not decide before the end of t + 1 rounds. A variant of the problem in which the set of input vectors is restricted is called condition-based consensus. In this setting, Mostéfaoui, Rajsbaum and Raynal defined a natural degree of restriction called the condition of the set of input vectors that a protocol is assumed to handle. The condition is a natural number d ⩽ t, with a larger condition implying a smaller set of input values. Moreover, they showed that condition-d consensus can be solved in t + 1 − d rounds in the worst case. Dwork and Moses considered simultaneous consensus, a variant of (unconditional) consensus in which all correct processes must decide in the same round. Like ordinary consensus, this problem can be solved in t + 1 rounds in the worst case. However, they showed that the stopping time depends on the pattern in which failures occur. They defined a notion of the waste W ( F ) of a failure pattern F (where 0 ⩽ W ( F ) ⩽ t − 1 ), and showed that t + 1 − W ( F ) rounds are necessary and sufficient for simultaneous consensus. They presented a solution that was optimal in all cases, and not just in the worst case: For every behavior of the adversary, their protocol stops as soon as any correct protocol can possibly stop. This paper considers condition-based simultaneous consensus in the synchronous model. 1 1 A preliminary version of this paper appeared at DISCʼ2008 (Moses and Raynal, 2008 [10]). It first presents a simple algorithm in which processes decide simultaneously at the end of the round R S t, d, F = ( t + 1 ) − max { W ( F ), d }. Then, the main result of the paper is presented, namely the statement and the proof that R S t, d, F is a lower bound for simultaneous condition-based consensus. This shows that, contrary to what could be hoped, when considering condition-based consensus with simultaneous decision, we can benefit from the best of both actual worlds (either the failure world when R S t, d, F = ( t + 1 ) − W ( F ), or the condition world when R S t, d, F = t + 1 − d ), but we cannot benefit from the sum of savings offered by both. Only the best discount applies. From a technical point of view, the lower bound result is based on two new notions associated with conditions on input vectors, called d-coverability and d-tightness.

TARK Conference 2011 Conference Paper

Known unknowns: time bounds and knowledge of ignorance

• Ido Ben-Zvi
• Yoram Moses

This paper studies the role that known bounds on message transmission times in a computer network play on the evolution of the epistemic state over time. A connection to cones of causal influence analogous to, and more general than, light cones is presented. Focusing on lower bounds on message transmission times, an analysis is presented of how knowledge about when others are guaranteed to be ignorant about an event of interest (“knowing that they don’t know”) can arise. This has implications in competitive settings, in which knowing about another’s ignorance can provide an advantage. The Happiness of Fish Chuangtse and Hueitse had strolled on to the bridge over the Hao, when the former observed: “See how the small fish are darting about! That is the happiness of the fish. ” “You not being a fish yourself, said Hueitse, “how can you know the happiness of the fish? ” “And you not being I, ” retorted Chuangtse, “ how can you know that I do not know? ” Chuangtse, circa 300 B. C.

TCS Journal 2010 Journal Article

Continuous consensus with ambiguous failures

• Tal Mizrahi
• Yoram Moses

Continuous consensus (CC) is the problem of maintaining up-to-date and identical copies of a “core” of information about the past at all correct processes in the system (Mizrahi and Moses, 2008 [6]). This is a primitive that supports simultaneous coordination among processes, and eliminates the need for issuing separate instances of consensus for different tasks. Recent work has presented new simple and efficient optimum protocols for continuous consensus in the crash and (sending) omissions failure models. For every pattern of failures, these protocols maintain at each and every time point a core that subsumes that maintained by any other continuous consensus protocol. This paper considers the continuous consensus problem in the face of harsher failures: general omissions and authenticated Byzantine failures. Computationally efficient optimum protocols for CC do not exist in these models if P ≠ N P. A variety of CC protocols are presented. The first is a simple protocol that enters every interesting event into the core within t + 1 rounds (where t is the bound on the number of failures), provided there are a majority of correct processes. The second is a protocol that achieves similar performance so long as n > t (i. e. , there is always guaranteed to be at least one correct process). The final protocol makes use of active failure monitoring and failure detection to include events in the core much faster in many runs of interest. Its performance is established based on a nontrivial property of minimal vertex covers in undirected graphs. The results are adapted to the authenticated Byzantine failure model, in which it is assumed that faulty processes are malicious, but correct processes have unforgeable signatures. Finally, the problem of uniform CC is considered. It is shown that a straightforward version of uniform CC is not solvable in the setting under study. A weaker form of uniform CC is defined, and protocols achieving it are presented.

IJCAI Conference 2007 Conference Paper

• Joseph Halpern
• Yoram Moses

We show how solution concepts in games such as Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium can be given a uniform definition in terms of knowledge-based programs. Intuitively, all solution concepts are implementations of two knowledge-based programs, one appropriate for games represented in normal form, the other for games represented in extensive form. These knowledge-based programs can be viewed as embodying rationality. The representation works even if (a) information sets do not capture an agent's knowledge, (b) uncertainty is not represented by probability, or (c) the underlying game is not common knowledge.

TARK Conference 2005 Conference Paper

Continuous consensus via common knowledge

• Tal Mizrahi
• Yoram Moses

LPAR Conference 2001 Conference Paper

A Refinement Theory that Supports Reasoning About Knowledge and Time

• Kai Engelhardt
• Ron van der Meyden
• Yoram Moses

Abstract An expressive semantic framework for program refinement that supports both temporal reasoning and reasoning about the knowledge of multiple agents is developed. The refinement calculus owes the cleanliness of its decomposition rules for all programming language constructs and the relative simplicity of its semantic model to a rigid synchrony assumption which requires all agents and the environment to proceed in lockstep. The new features of the calculus are illustrated in a derivation of the two-phase-commit protocol.

TARK Conference 1998 Conference Paper

Knowledge and the Logic of Local Propositions

• Kai Engelhardt
• Ron van der Meyden
• Yoram Moses

An agent's limited view of the state of a distributed system may render globally different situations indistinguishable. A proposition is local for this agent whenever his view suffices to decide this proposition. Motivated by a framework for the development of distributed programs from knowledge-based specifications, we introduce a modal logic of local propositions, in which it is possible to quantify over such propositions. We show that this logic is able to represent a rich set of epistemic notions. Under the usual strong semantics, this logic is not recursively axiomatizable, however. We show that by weakening the semantics of quantification, it is possible to obtain a logic that is axiomatizable and is still able to express interesting epistemic notions.

TARK Conference 1998 Conference Paper

Using Counterfactuals in Knowledge-Based Programming

• Joseph Y. Halpern
• Yoram Moses

We show how counterfactuals can be added to the framework of knowledgebasedprogramsofFagin, Halpern, Moses, and Vardi [1995, 1997]. We show that counterfactuals allowus to capture in a natural waynotions like minimizingthe numberof messages that are sent, whereas attempts to formalize these notions without counterfactuals lead to some rather counterintuitivebehavior. We also show how knowledge-basedprograms with counterfactuals can capture subgame-perfectequilibria in games of perfect information.

TARK Conference 1996 Conference Paper

Common Knowledge Revisited

• Ronald Fagin
• Joseph Y. Halpern
• Yoram Moses
• Moshe Y. Vardi

We consider the common-knowledge paradox raised in [HM90]: common knowledge is necessary for coordination, but common knowledge is unattainable in the real world because of temporal imprecision. We discuss two solutions to this paradox: (1) modeling the world with a coarser granularity, and (2) relaxing the requirements for coordination.

AIJ Journal 1996 Journal Article

Off-line reasoning for on-line efficiency: knowledge bases

• Yoram Moses
• Moshe Tennenholtz

The complexity of reasoning is a fundamental issue in AI. In many cases, the fact that an intelligent system needs to perform reasoning on-line contributes to the difficulty of this reasoning. This paper considers the case in which an intelligent system computes whether a query is entailed by the system's knowledge base. It investigates how an initial phase of off-line preprocessing and design can improve the on-line complexity considerably. The notion of an efficient basis for a query language is presented, and it is shown that off-line preprocessing can be very effective for query languages that have an efficient basis. The usefulness of this notion is illustrated by showing that a fairly expressive language has an efficient basis. A dual notion of an efficient disjunctive basis for a knowledge base is introduced, and it is shown that off-line preprocessing is worthwhile for knowledge bases that have an efficient disjunctive basis.

TARK Conference 1994 Conference Paper

Algorithmic Knowledge

• Joseph Y. Halpern
• Yoram Moses
• Moshe Y. Vardi

The standard model of knowledge in multi-agent systems suffers from what has been called the logical omniscience problem: agents know all tautologies, and know all the logical consequences of their knowledge. For many types of analysis, this turns out not to be a problem. Knowledge is viewed as being ascribed by the system designer to the agents; agents are not assumed to compute their knowledge in any way, nor is it assumed that they can necessarily answer questions based on their knowledge. Nevertheless, in many applications that we are interested in, agents need to act on their knowledge. In such applications, an externally ascribed notion of knowledge is insufficient: clearly an agent can base his actions only on what he explicitly knows. Furthermore, an agent that has to act on his knowledge has to be able to compute this knowledge; we do need to take into account the algorithms available to the agent, as well as the "effort" required to compute knowledge. In this paper, we show how the standard model can be modified in a natural way to take the computational aspects of knowledge into account. *Current address: Dept. of Computer Science, Rice University, P. O. Box 1892, Houston, TX 77251-1892,

AAAI Conference 1994 Conference Paper

An Operational Semantics for Knowledge Bases

• Ronald Fagin
• Yoram Moses

The standard approach in AI to knowledge representation is to represent an agent’ s knowledge symbolically as a collection of formulas, which we can view as a knowledge base. An agent is then said to know a fact if it is provable from the formulas in his knowledge base. Halpern and Vardi advocated a model-theoretic approach to knowledge representation. In this approach, the key step is representing the agent’ s knowledge using an appropriate semantic model. Here, we model knowledge bases operationally as multi-agent systems. Our results show that this approach offers significant advantages.

TARK Conference 1994 Conference Paper

Knowledge as a Tool in Motion Planning and Uncertainty

• Ronen I. Brafman
• Jean-Claude Latombe
• Yoram Moses
• Yoav Shoham

Inspired by the success of the distributed computing community in applying logics of knowledge and time to reasoning ahout distributed protocols, we aim for a similarly powerful and high-level abstraction when reasoning about control problems involving uncertainty. Here we concentrate on robot motion planning, with uncertainty in both control and sensing. This problem has already been well studied within the robotics community. Our contributions include the following: • We define, a new, naturM problem in this domain: obtaining a sound and complete termination condition, given initial and goal locations. • We define a high-level language, a logic of time and knowledge, to reason about motion plans in the presence of uncertainty, and use it to provide general conditions for the existence of sound and complete termination conditions for a broad class of motion plans. ®We characterize the optimal sound termination conditions for the general problem, relate them to a class of fundamental knowledge based protocols and provide a natural example of knowledge based protocols lacking a canonical implementation. 1 *Currently on sabbatical at the Oxford University Computing Laboratory, Oxford OX1 3QD England: The first part of this paper generalizes results of a previous paper by Brafman, I, atombe and Shoham ([BLS93]). Sections 4. 3 and 5 contain ne'w ~aterial.

AIJ Journal 1993 Journal Article

Belief as defeasible knowledge

• Yoram Moses
• Yoav Shoham

We investigate the relation between the notions of knowledge and belief. Contrary to the well-known slogan about knowledge being “justified, true belief”, we propose that belief be viewed as defeasible knowledge. We offer several related definitions of belief as knowledge-relative-to-assumptions, and provide complete axiomatic systems for the resulting notions of belief. We also show a close tie between our definitions and the literature on nonmonotonic reasoning. Our definitions of belief have several advantages. First, they are short. Second, we do not need to add anything to the logic of knowledge: the “right” properties of belief fall out of our definitions and the properties of knowledge. Third, the connection between knowledge and belief is derived from one fundamental principle. Finally, a major attraction of logics of knowledge in computer science has been the concrete grounding of the mental notion in objective phenomena; by reducing belief to knowledge we obtain this grounding for a notion of belief.

STOC Conference 1993 Conference Paper

Fully polynomial Byzantine agreement in t+1 rounds

• Juan A. Garay 0001
• Yoram Moses

IJCAI Conference 1993 Conference Paper

Off-line Reasoning for On-line Efficiency

• Yoram Moses
• Moshe Tennenholtz

The complexity of reasoning is a fundamental issue in A I. In many cases, the fact that an intelligent system needs to perform reasoning on-line contributes to the difficulty of this reasoning. In this paper we investigate a couple of contexts in which an initial phase of off-line preprocessing and design can improve the on-line complexity considerably. The first context is one in which an intelligent system computes whether a query is entailed by the system's knowledge base. We present the notion of an efficient basts for a query language, and show that off-line preprocessing can be very effective for query languages that have an efficient basis. The usefulness of this notion is illustrated by showing that a fairly expressive language has an efficient basis. The second context is closely related to the artificial social systems approach introduced in [MT90]. We present the design of a social law for a multi-agent environment as primarily an instance of off-line processing, and study this problem in a particular model. We briefly review the artificial social systems approach to design of multi-agent systems, introduced in [MT90]. Computing or coming up with a social law is viewed as a primarily off-line activity that has major impact on the effectiveness of the on-line activity of the agents. The tradeoff' between the amount of effort invested in computing the social law and the cost of the on-line activity can thus be viewed as an off-line vs. on-line tradeoff.

AIJ Journal 1992 Journal Article

A guide to completeness and complexity for modal logics of knowledge and belief

• Joseph Y. Halpern
• Yoram Moses

We review and re-examine possible-worlds semantics for propositional logics of knowledge and belief with three particular points of emphasis: (1) we show how general techniques for finding decision procedures and complete axiomatizations apply to models for knowledge and belief, (2) we show how sensitive the difficulty of the decision procedure is to such issues as the choice of modal operators and the axiom system, and (3) we discuss how notions of common knowledge and distributed knowledge among a group of agents fit into the possible-worlds framework, As far as complexity is concerned, we show, among other results, that while the problem of deciding satisfiability of an S5 formula with one agent is NP-complete, the problem for many agents is PSPACE-complete. Adding a distributed knowledge operator does not change the complexity, but once a common knowledge operator is added to the language, the problem becomes complete for exponential time.

TARK Conference 1992 Conference Paper

Knowledge and Communication

• Yoram Moses

The subtle interaction between knowledge, action, and communication is an important theme underlying much of the literature on reasoning about knowledge in a variety of disciplines. The purpose of this paper is to review work on the relationship between knowledge and communication in distributed systems. Communication is the basic means by which knowledge is obtained and transferred in a distributed system. As a result, properties of the communication medium play a central role in determining what states of knowledge can result from communication. Most of this paper is a review of theorems that illustrate this connection and a discussion of their implications. In the latter part of this paper, we consider knowledge-orientedprogramming, a novel approach to describing agents' behavior in a distributed system. Knowledge-oriented programs are an extension of the knowledge-based protocols of Halpern and Fagin, in which communication is abstracted away completely from the description of agents' behavior. In its stead, agents can perform high level actions that are defined in terms of changing the state of knowledge of other agents. Such actions are called knowledge-orientedactions. Communication then enters when we come to implement the knowledge-oriented actions in a given context. Knowledge-oriented programming makes explicit use of the fact that the role of communication is to change the state of knowledge of agents in the system.

TARK Conference 1990 Conference Paper

Agreeing to Disagree After All

• Yoram Moses
• Gal Nachum

Bacharach and Cave independently generalized Aumann's celebrated agreement theorem to the case of decision functions. Roughly speaking, they showed that once two like-minded agents reach common knowledge of the actions each of them intends to perform, they will perform identical actions. This theorem is proved for decision functions that satisfy a condition that Bacharach calls the sure thing condition, which is closely related to Savage's sure thing principle. The assumption that any reasonable decision function should satisfy the sure thing condition seems to have been widely accepted as being natural and intuitive. By taking a closer look at the meaning of the sure thing condition in this context', we argue that the technical definition of the sure thing condition does not capture the intuition behind Savage's sure thing principle very well. It seems to involve nontrivial hidden assumptions, whose appropriateness in the case of non-probabilistic decision functions is questionable. Similar trouble is found with the technical definition of the like-mindedness of two agents. Alternative definitions of the sure thing principle and like-mindedness are suggested, and it is shown that the agreement theorem does not hold with respect to these definitions. In particular, it is shown that the agreement theorem does not apply to a particularly appealing example attributed to Bacharach. Conditions that do guarantee the agreement theorem for decision functions are presented. Finally, we consider similar issues that arise in the case of communication among more than two agents, as studied by Parikh and Krasucki.

I&C Journal 1990 Journal Article

Knowledge and common knowledge in a Byzantine environment: Crash failures

• Cynthia Dwork
• Yoram Moses

By analyzing the states of knowledge that the processors attain in an unreliable system of a simple type, we capture some of the basic underlying structure of such systems. In particular, we study what facts become common knowledge at various points in the execution of protocols in an unreliable system. This characterizes the simultaneous actions that can be carried out in such systems. For example, we obtain a complete characterization of the number of rounds required to reach simultaneous Byzantine agreement, given the pattern in which failures occur. From this we derive a new protocol for this problem that is optimal in all runs, rather than just always matching the worst-case lower bound. In some cases this protocol attains simultaneous Byzantine agreement in as few as two rounds. We also present a nontrivial simultaneous agreement problem called bivalent agreement for which there is a protocol that always halts in two rounds. Our analysis applies to simultaneous actions in general, and not just to Byzantine agreement. The lower bound proofs presented here generalize and simplify the previously known proofs.

IJCAI Conference 1989 Conference Paper

Belief as Defeasible Knowledge

• Yoav Shoham
• Yoram Moses

IJCAI Conference 1989 Conference Paper

On Cooperation in a Multi-Entity Model

• Moshe Tennenholtz
• Yoram Moses

STOC Conference 1988 Conference Paper

A Knowledge-Based Analysis of Zero Knowledge (Preliminary Report)

• Joseph Y. Halpern
• Yoram Moses
• Mark R. Tuttle

FOCS Conference 1988 Conference Paper

Coordinated Traversal: (t + 1)-Round Byzantine Agreement in Polynomial Time

• Yoram Moses
• Orli Waarts

The problem of efficiently performing Byzantine agreement in t+1 rounds in the face of arbitrarily malicious failures is treated. A communication-efficient polynomial-time protocol is presented for n>8t. The protocol is an early stopping protocol, halting in min(t+1, f+2) rounds in the worst case, where f is the number of processors that fail during the run. This is provably optimal. The protocol is based on a careful combination of early stopping, fault masking, and a technique called coordinated traversal. The combination of the three provides a powerful method for restricting the damage that a faulty processor, however malicious, can do. One of the byproducts of this protocol is a polynomial-time (t+1)-round protocol for the Byzantine firing squad problem. >

TARK Conference 1988 Conference Paper

Resource-bounded Knowledge

• Yoram Moses

Traditional treatments of knowledge in distributed systems have not been able to account for processors' limited computational resources. This paper presents definitions of resource-bounded knowledge, belief, and common knowledge that in a precise sense capture the behavior of resource-bounded processors. Subtle properties of the resulting notions are discussed, and they are successfully a. pplied to two problems in distributed computing.

TARK Conference 1986 Conference Paper

Knowledge and Common Knowledge in a Byzantine Environment I: Crash Failures

• Cynthia Dwork
• Yoram Moses

By analyzing the states of knowledge that the processors attain in an unreliable system of asimple type, we capture some of the basic underlying structure of such systems. The analysis provides us with a better understanding of existing protocols for problems such as Byzantine agreement, generalizes them considerably, and facilitates the design of improved protocols for many related problems.

FOCS Conference 1986 Conference Paper

Programming Simultaneous Actions Using Common Knowledge: Preliminary Version

• Yoram Moses
• Mark R. Tuttle

This work applies the theory of knowledge in distributed systems to the design of faulttolerant protocols for problems involving coordinated simultaneous actions in synchronous systems. We give a simple method for transforming specifications of such problems into high-level protocols programmed using explicit tests of whether certain facts are common knowledge. The resulting protocols are optimal in all runs: for every possible input to system and pattern of processor failures, they are guaranteed to perform the simultaneous actions as soon as any other protocol can possibly perform them. A careful analysis of when facts become common knowledge shows how to efficiently implement these protocols in many variants of the omissions failure model. In the generalized omissions model, however, it is shown that any protocol that is optimal in this sense must require co-NP hard computations. The analysis in this paper exposes subtle differences between the failure models, including the precise point at which this gap in complexity occurs.

NMR Workshop 1984 Conference Paper

Towards a Theory of Knowledge and Ignorance: Preliminary Report

• Joseph Y. Halpern
• Yoram Moses