320 C. DWORK ET AL. (a) For the fail-stop model, ifN 2 t, then Algorithm 4l achieves Consistency, strong unanimity, and termination for an arbitrary value domain. (b) For Byzantine faults with authentication, if N I 2t + 1, then Algorithm 5’ achieves consistency, weak unanimity, and termination for an arbitrary value domain. (c) For Byzantine faults with authentication, ifN 2 2t + 1 and ifthe general signs the initial values, then Algorithm 6’ achieves consistency, strong unanimity, and termination for an arbitrary value domain. 6.4 UPPER BOUNDS FOR PHI UNKNOWN. The strategy is the same as in Sections 4.2 and 5.4. Namely, we use the algorithm of Section 6.3 where R, = 3Nr + 6r + 3A + 3 steps are allowed for the simulation of round r, where R, is obtained from the R of Section 6.3 by replacing @ by r. It is important to note that the verification of (a) in Section 6.3 (viz., that if a signal is received by pi at round r, then all messages sent by pi during round r to correct processors arrive before the other processor starts any round greater than r) did not depend in any way on a. Therefore, (a) holds even for rounds r, where r is smaller than the actual (unknown) 9 that holds in the run. Applying this transformation to Algorithms 4, 5, and 6, we obtain Algorithms 42, 52, and 62, respectively. THEOREM 6.4. Assume that communication is synchronous and processors are partially synchronous (phi is unknown). Then claims (a), (b), and (c) of Theorem 6.3 holdfor Algorithms 42, 52, and 62, respectively. Our claim of a. polynomial time bound (after GST) for the algorithms of Sections 6.3 and 6.4 follows from clock property (A3.2), which states that the master clock runs fast enough afier GST. We should also mention that Remark 5 at the end of Section 5 does not apply to the simulations of Sections 6.3 and 6.4. Here, if a processor’s clock makes a big jump so that rounds are missed, all steps of the consensus protocol during the missed round(s) must be simulated. If the correct pi sends a message to a correct pj and receives a signal during round r, then pj must receive the message and make the appropriate state transition caused by this reception, even if pi’s clock makes a large jump that causes it to miss round r. 6.5 LOWER BOUNDS. The following lower bound shows that the resiliency of Theorems 6.3 and 6.4, parts (b) and (c), cannot be improved. The method used to prove this lower bound was suggested by Dolev (personal communication). THEOREM 6.5. Assume the model with Byzantine faults with authentication, synchronous communication, and partially synchronous processors. Assume 4 I N 5 2t. Then there is no t-resilient consensus protocol that achieves weak unanimity for binary values, even tf the general signs the initial values. PROOF. Assume, to the contrary, that a consensus algorithm exists. The proof is identical for both variations of partially synchronous processors. In the following we assume, without loss of generality, that all messages are delivered in one real- time step. Divide the processors into four groups P, Q, (b ), and (r J, where groups P and Q each contain at least 1 and at most t - 1 processors and where b and r are single processors. We say that a processor wakes up at real time s if it takes the first step of its protocol at real time s. We say that a processor runs fast in the real- time interval [s,, s2J if it takes a step of its protocol at each real-time step in the interval.