294 C. DWORK ET AL. Omission: Faulty processor pi follows its protocol correctly, but Send(m, pj), when executed by pi, might not place m in pj’s buffer and Receive(pi) might cause only a subset of the delivered messages to be actually received by pi. In other words, an omission fault on reception occurs when some set S of messages is delivered to pi and all messages in S are removed from pi’s buffer, but pi follows a state transition as though some (possibly empty) subset S’ of S were delivered. Authenticated Byzantine: Arbitrary behavior, but messages can be signed with the name of the sending processor in such a way that this signature cannot be forged by any other processor. Byzantine: Arbitrary behavior and no mechanism for signatures, but we assume that the receiver of a message knows the identity of the sender. 2.3 PARTIAL SYNCHRONY. Let I be an interval of real time and R be a run. We say that the communication bound A holds in Ifor run R provided that, if message m is placed in pj’s buffer by some Send(m, pj) at a time s1 in I, and if pj executes a Receive(pj) at a time s2 in I with s2 2 s1 + A, then m must be delivered to pj at time s2 or earlier. This says intuitively that A is an upper bound on message transmission time in the interval I. The processor bound @ holds in Ifor R provided that, in any contiguous subinterval of I containing @ real-time steps, every correct processor must take at least one step. This implies that no correct processor can run more than @ times slower than another in the interval I. The following conditions, which define varying degrees of communication synchrony, place constraints on the kinds of runs that are allowed. In these definitions, A denotes some particular positive integer: (1) A is known: The communication bound A holds in [ 1, 00) for every run R. Delta is known: A is known for some fixed A. This is the usual definition of synchronous communication. (2) Delta is unknown: For every run R, there is a A that holds in [ 1, m). (3) A holds eventually: For every run R, there is a time T such that A holds in [T, m). Such a time T is called the Global Stabilization Time (GST). Delta holds eventually: A holds eventually for some fixed A. If either (2) or (3) holds, we say that communication is partially synchronous. It is helpful to view each situation as a game between a protocol designer and an adversary. If delta is known, the adversary names an integer A, and the protocol designer must supply a consensus protocol that is correct if A always holds. If delta is unknown, the protocol designer supplies the consensus protocol first, then the adversary names a A, and the protocol must be correct if that A always holds. If delta holds eventually, the adversary picks A, the designer (knowing A) supplies a consensus protocol, and the adversary picks a time T when A must start holding. By replacing A by @ and “delta” by “phi” above, (1) defines synchronous processors, and (2) and (3) define two types of partially synchronous processors. 2.4 CORRECTNESS OF A CONSENSUS PROTOCOL. Given assumptions A about processor and communication synchrony, a fault type F, and a number N of processors and an integer t with 0 5 t I N, correctness of a t-resilient consensus protocol is defined as follows: For any set C containing at least N - t processors and any run R satisfying A and in which the processors in C are correct and the behavior of the processors not