C. DWORK ET AL. 306 delivered. In the modified scenario, the processors in P still decide 1, contradicting weak unanimity. Consider Scenario B: All initial values are 1, the processors in P are initially dead, and messages sent from Q to Q are delivered in exactly time 1. By a similar argument, the processors in Q decide 1 within TB steps for some finite TB. Consider Scenario C (for Contradiction): Processors in P have initial values 0, processors in Q have initial values 1, all processors are alive, messages sent from P to P or from Q to Q are delivered in exactly time 1, and messages sent from P to Q or from Q to P take more than max( TA, TB) steps to be delivered. The processors in group P (respectively, group Q) act exactly as they do in Scenario A (respectively, Scenario B). This yields a contradiction. Cl The following lower bound result again applies in the case of weak unanimity and a binary value domain. It shows that the resiliency of Theorems 4.1 and 4.2, part (b), cannot be improved, even for the case of weak unanimity and a binary value domain. THEOREM 4.4. Assume the model with Byzantine faults and authentication, in which the processors are synchronous and communication is partially synchronous (either delta holds eventually or delta is unknown). Assume 2 5 NI 3t. Then there is no t-resilient consensus protocol that achieves weak unanimity for binary values. PROOF. Again, the proof is the same for both definitions of partially synchron- ous communication. Assume the contrary. We shall derive a contradiction. If N = 2, then the theorem follows from the previous lower bound, Theo- rem 4.3. Assume then that N L 3. Divide the processors into three groups, P, Q, and R, each with at least 1 and at most t processors. First consider the following Scenario A: All initial values are 0, the processors in R are initially dead, and all messages sent from processors in P U Q to processors in P U Q are delivered in exactly time 1. By t-resiliency, the processors in P U Q must reach a decision; say that this occurs within time TA. As in the previous lower bound proof, the decision must be 0. Consider Scenario B: All initial values are I, the processors in P are initially dead, and messages sent from Q U R to Q U R are delivered in exactly time 1. By a similar argument, the processors in Q U R decide 1 within TB steps for some finite TB. Consider Scenario C: Processors in P have initial values 0, processors in R have initial values 1, and processors in Q are faulty. The processors in Q behave with respect to those in P exactly as they do in Scenario A, and with respect to those in R exactly as they do in Scenario B. The messages sent from P to P U Q and from R to R U Q are delivered in exactly time 1, but all messages from P to R or from R to P take more than max(TA, TB) steps to be delivered. The processors in group P (respectively, group R) act exactly as they do in Scenario A (respectively, Scenario B). This yields a contradiction. Cl The preceding lower bound is tight for the case of unauthenticated Byzantine faults (Theorems 4.1 and 4.2, part (c)). 5. Partially Synchronous Communication and Processors In this section we consider the case in which both communication and processors are partially synchronous. We show the existence of protocols with the same resiliencies as in the previous section, where only communication was partially