Consensus in the Presence of Partial Synchrony 293 The remainder of this paper is organized as follows: Section 2 contains delini- tions. Section 3 contains our basic protocols, presented in a basic round model, which has more power than the models in which we are really interested. Section 4 contains our results for the model in which processors are synchronous and communication is partially synchronous. In particular, the protocols of Sec- tion 3 are adapted to this model. The distributed clocks are defined in Section 5, where we also discuss how to combine the results of Section 3 with the clocks to produce protocols for the model in which both processors and communication are partially synchronous. Section 6 contains our results for the case in which processors are partially synchronous and communication is synchronous. 2. Definitions 2.1 MODEL OF COMPUTATION. Our formal model of computation is based on the models of [4] and [lo]. Here we review the basic features of the model informally. The communication system is modeled as a collection of N sets of messages, called bu@s, one for each processor. The buffer ofpi represents messages that have been sent to pi, but not yet received. Each processor follows a deterministic protocol involving the receipt and sending of messages. Each processor pi can perform one of the following instructions in each step of its protocol: Send(m, pj): places message m in p:s buffer; Receive(pi): removes some (possibly empty) set S of messages from p;s buffer and delivers the messages to pi. In the Send(m, pi) instruction, pj can be any processor; that is, the communication network is completely connected. A processor’s protocol is specified by a state transition diagram; the number of states can be infinite. The instruction to be executed next depends on the current state, and the execution causes a state transition. For a Send instruction, the next state depends only on the current state, whereas, for a Receive instruction, the next state depends also on the set S of delivered messages. The initial state of a processor pi is determined by its initial value vi in V. At some point in its computation, a processor can irreversibly decide on a value in V. For subsequent definitions, it is useful to imagine that there is a real-time clock outside the system that measures time in discrete integer-numbered steps. At each tick of real time, some processors take one step of their protocols. A run of the system is described by specifying the initial states for all processors and by specifying, for each real-time step, (1) which processors take steps, (2) the instruction that each processor executes, and (3) for each Receive instruction, the set of messages delivered. Runs can be finite or infinite. Given an infinite run R, the message m is lost in run R if m is sent by some Send(m, pj), pj executes infinitely many Receive instructions in R, and m is never delivered by any Receive(pj). 2.2 FAILURES. A processor executes correctly if it always performs instructions of its protocol (transition diagram) correctly. A processor is correct if it executes correctly and takes infinitely many steps in any infinite run. We consider four types of increasingly destructive faulty behavior of processor pi: Fail-stop: Processor pi executes correctly, but can stop at any time. Once stopped it cannot restart.