Consensus in the Presence of Partial Synchrony 303 Since processors operate in lock-step synchrony, it is useful to imagine that each (correct) processor has a clock that is perfectly synchronized with the clocks of other correct processors. Initially, the clock is 0, and a processor increments its clock by 1 every time it takes a step. The assumption @ = 1 implies that the clocks of all correct processors are exactly the same at any real-time step. As presented in Section 2, there are two different definitions of partially syn- chronous communication: (1) delta is unknown, and (2) delta holds eventually. We consider these two cases separately. Section 4.1 describes the upper bound results for the model in which delta holds eventually. Section 4.2 describes the upper bound results for delta unknown. Finally, Section 4.3 contains the lower bound results. 4.1 UPPER BOUNDS WHEN DELTA HOLDS EVENTUALLY. We first consider the model in which delta holds eventually. Fix any of the four possible fault models. We show that, if there is a t-resilient consensus protocol in the basic model, then there is one in the model in which delta holds eventually. To see the implication, fix A and assume algorithm A works for the basic model. From A we define an algorithm A ’ for the model in which A holds eventually. Let R = N + A. Each processor divides its steps into groups of R, and uses each group to simulate its own actions in a single round of algorithm A. More specifically, the processor uses the first N steps of group r to send its round r messages to the N processors, sending to one processor at a time, and uses the last A steps to perform Receive operations. The state transition for round r is simulated at the last step of group r. (The number R is large enough to allow all processors to exchange messages within a single group of steps, once GST has been reached.) Each processor always attaches a round identifier (number) to messages, and any message sent during a round r that arrives late during some round r’ > r is ignored. Thus, communication during each round is independent of communication during any other round. For any run e’ of A ‘, it is easy to show that there exists a corresponding run e of A with the following properties: (1) All processors that are correct in e’ are also correct in e. (2) The types of faults exhibited by the faulty processors are the same in e’ as in e. (3) Every state transition of a correct processor in e is simulated by the correspon- ding correct processor in e’. Since algorithm A is assumed to be a t-resilient consensus protocol for the basic round model, consensus is eventually reached in e, and so in e’, as needed. By applying the transformation just described to Algorithms 1-3, we obtain Algorithms 1 l-3’, respectively. We immediately obtain the following result: THEOREM 4.1. Assume that processors are completely synchronous (@ = 1) and communication is partially synchronous (A holds eventually). (a) For the fail-stop or omission fault model, if N > 2t + 1, then Algorithm 1’ achieves consistency, strong unanimity, and termination for an arbitrary value domain. (6) For the authenticated Byzantine fault model, ifN z 3t + 1, then Algorithm 2’ achieves consistency, strong unanimity, and termination for an arbitrary value domain.