Consensus in the Presence of Partial Synchrony 313 messages, and it simulates the receipt of all the messages that are in the algorithm message buffer. For any run e’ of A ‘, it is easy to define a corresponding run e of A. We see that all processors that are correct in e’are also correct in e, and that the types of faults exhibited by the faulty processors are the same in both cases. We argue that, within a short time after GST, the number of ticks in e’ that are allotted for the simulation of any round r is sufficient to allow all round r messages to be sent and received. More precisely, the “short time after GST” is chosen so that parts (a) and (b) of Lemma 5.7 hold. We must first show that there is sufficient time for each correct processor pi to send all its round r messages and then to do at least one Receive operation. Assume that s is the first real time at which processor p;s private clock reaches or exceeds (r - l)R. Then processorpi would finish sending all its round r messages and doing one Receive operation by real time s + 3(N + l)+. We must show that processor pi’s clock up to real time s + 3(N + I)+ remains less than rR, that is, that Ci(S + 3(N + I)+) < rR. (5.1) We must also show that there is sufficient time for all round r messages sent by processor pi to be received. Fix a correct processor pi. We show that processor pj has sufficient time to receive a round r message from processor pi before going on to simulate round r + 1. Again, letting s be the first real time for which ci(S) 2 (r - l)R, pi will send the message to pj by real time s + 3N@, and pj will receive the message by real time s + 3N+ + D. Therefore, we must show that Cj(S + 3N@ + D) < rR. (5.2) Since D 2 3@ and since clocks are nondecreasing, we can prove both (5.1) and (5.2) by showing that, for any correct processor pk, ck(s + 3N9 + D) < rR. This follows because ck(s + 3N+ + D) 5 c(S + 3N9 + D) (by Lemma 5.1) 5 C(s - 1) + 3N+ + D + 1 (by Lemma 5.3) I Ci(S - 1) + 3N@ + 20 + 2 (by Lemma 5.7(a)) < (r - 1)R + 3N9 + 20 + 2 (by assumption) = rR. Since A is assumed to be a t-resilient consensus protocol for the basic 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 13-33, respectively. We immediately obtain the following result: THEOREM 5.1. Assume that communication and processors are partially syn- chronous (delta and phi hold eventually). (a) For the fail-step or omission fault model, if N 2 2t + 1, then Algorithm l3 achieves consistency, strong unanimity, and termination for an arbitrary value domain. (b) For the authenticated Byzantine fault model, ifN 2 3t + 1, then Algorithm 23 achieves consistency, strong unanimity, and termination for an arbitrary value domain.