314 C. DWORK ET AL. (c) For the unauthenticated Byzantine fault model, ifN I 3t + 1, then Algorithm 33 achieves consistency, strong unanimity, and termination for an arbitrary value domain. As before, we claim that Algorithms 13-33 reach agreement within a polynomial (in N, A, and a) amount of time after GST. Our claims of polynomial-time performance follow from the fact that the master clock, a short time after GST, runs at a rate no slower than 1/(24NQ + 3(A + 39)) times real time (see Lemma 5.7(b)). Finally, the total number of message bits sent by correct processors is polynomially bounded in N, A, a’, and GST, since the number of bits in each message sent by a correct processor is polynomially bounded in these quantities. 5.4 UPPERBOUNDSWHEN DELTA ANDPHIAREUNKNOWN. Next,wepresent our upper bound results for partially synchronous communication and processors, for the model where delta and phi are unknown. The ideas are a simple combination of ideas from Sections 4.2 and 5.3. The transformation of a consensus protocol for the basic model to one for the model where delta and phi are unknown is identical to the transformation described in Section 5.3 except that the bound R, = 3Nr + 8r + 2 is used to describe the number of ticks to be used for the simulation of round r. (This bound is obtained from the previous bound by replacing both A and Q, by r.) The proof of correctness is the same as before, since GST is reached when r exceeds the (unknown) A and @ that hold in the run. By applying this transformation to Algorithms l-3, we obtain Algorithms 14-34, respectively. THEOREM 5.2. Assume that communication and processors are partially syn- chronous (delta and phi are unknown). Then claims (a)-(c) of Theorem 5.1 hold for Algorithms 1 4-3 4, respectively. As before, it is easy to see that Algorithms 14-34 reach agreement within a polynomial (in N, A, and a) amount of time. Remark 5. In the simulation of the basic model described in Sections 5.3 and 5.4, if the round number of processor p;s last algorithm simulation step was h and processor pi updates its clock and finds that it is now simulating some round k > h, then all state transitions in rounds h through k - 1 are simulated (except that no messages are sent). For a general simulation of the basic model, these transitions must all be simulated, since they may involve state transitions that processor pi must make in order that the simulation of the algorithm in the basic model be correct. However, it is not hard to see that, for the particular Algorithms l-3 designed for the basic model in Section 3.2, processor pi can just simulate the state transition for round h and continue the simulation at round k, without simulating the “missed” transitions in rounds h + 1 through k - 1. This can be done since the state information in Algorithms l-3 (not including the current round number) consists of the PROPER sets, the values which are locked, and other information associated with each lock. Changes in this state information are caused only by the receipt of certain messages. Since we have shown consistency for Algorithms l-3 even if messages are lost before GST, it follows that the algorithms remain consistent if processors, including correct ones, skip state transitions before GST. 6. Partially Synchronous Processors and Synchronous Communication In this section we consider models where processors are partially synchronous and communication is synchronous; that is, there is a fixed upper bound A on message