312 C. DWORK ET AL. From this lemma and the definition of the protocol, it follows easily that any tick or claim sent by a correct processor at time s can be encoded in O(t log C(s)) bits. Remark 4. The clocks of Sections 5.1 and 5.2 are similar to the one discovered independently by Attiya et al. [I]. 5.3 UPPER BOUNDS WHEN DELTA AND PHI HOLD EVENTUALLY. We now present our upper bound results for partially synchronous communication and processors, for the model where delta and phi hold eventually. Fix any of the four possible fault models. We show that, if there is a t-resilient protocol in the basic model, then there is one in the model where delta and phi hold eventually. To see the implication, fix A and a’, and assume algorithm A works for the basic model. We define A ’ from A as follows, so that A ’ works for the model where A and + hold after GST. As described above, two out of every three steps of each processor are used to maintain a distributed clock, and the other step is used to simulate algorithm A. For fail-stop or omission faults, we use the authenticated Byzantine clock, simplified appropriately because the signatures are not needed and because we cannot assume the authentication capability. Note that the consensus protocol and distributed clock protocol have the same constraint on the number of processors, N > 2t + 1. For unauthenticated Byzantine faults, we use the unauthenticated Byzantine clock. For authenticated Byzantine faults, either clock could be used. The Receive steps of algorithm A ’ are designated as belonging to either the clock simulation or the algorithm simulation. However, each time a Receive step of A ’ occurs, it is possible that messages for either or both simulations will be received. We assume that each processor maintains a pair of message buffers, one for each of the two simulations it is carrying out. When the processor does a Receive step that belongs to the clock simulation, it saves any messages for the algorithm simulation in the algorithm message buffer, and vice versa. Also, each time the processor does a Receive step that belongs to the clock simulation, it collects not only the new incoming messages, but all those in the clock message buffer, to use in its clock simulation step; analogous assumptions are made for the algorithm simulation. Fix R = 3N@ + 20 + 2, where, as before, D = A + 3@. Each processor uses its private clock to determine the round of algorithm A currently being simulated. Namely, if (r - l)R I Cl(S) < rR, then processor pi determines at real time s that the current round is Y. Processors label messages with round numbers. As long as a processor determines that the current round is r, it uses its protocol simulation steps to simulate steps of round Y in the basic model. The first Nprotocol simulation steps are used for sending the round Y messages to all the processors, and the remaining steps are spent executing Receive operations. Unlike the simulations in Section 4, it is possible that there will be insufficient time for a processor to actually send all its round r messages. Processor pi simulates its state transition for round r at its first algorithm simulation step at which it decides the current round is strictly greater than r. More specifically, assume that processor pi has reached an algorithm simulation step s, at which the current round is k, and assume that the round at processor p;s last algorithm simulation step was h < k. Then processor pi simulates its state transitions forroundsh,h+ I,..., k - 1, all at the beginning of step s. In simulating these state transitions, processor pi simulates all of its sending steps for these rounds; that is, it makes the appropriate state transitions, but does not actually send any