322 C. DWORK ET AL. THEOREM 6.6. Assume the model with omission faults, synchronous commu- nication, and partialIy synchronous processors. Assume 3 I N s 2t - I. Then there is no t-resilient consensus algorithm that achieves weak unanimity for binary values. For the case of strong unanimity and Byzantine faults with authentication, but where the initial values are not signed by a general, Theorems 5.1 and 5.2, part (b), give consensus algorithms if N L 3t + 1. The following shows that this resiliency is the best possible for this case. THEOREM 6.7. Assume the model with Byzantine faults with authentication, synchronous communication, and partially synchronous processors. Assume 3 5 N 5 3t. If the general does not sign the initial values, there is no t-resilient consensus protocol that achieves strong unanimity for binary values. PROOF. Assume N I 3t. Divide the processors into three groups, P, Q, and R, each containing at least 1 and at most t processors. Consider the following Scenario A: Processors in P have initial values 0, proces- sors in Q have initial values 1, processors in P U Q wake up at time 1 and run fast thereafter, and processors in R are initially dead. Therefore, the processors in P U Q must make some decision after some finite time. By symmetry we can assume, without loss of generality, that they decide 1 within time TA. Consider Scenario B: All processors have initial values 0, processors in R are correct but do not wake up until after time TA, and processors in Q are Byzantine and behave with respect to P exactly as they do in Scenario A. The processors in group P act exactly as they do in Scenario A, so they decide 1. This contradicts strong unanimity. Cl 7. Open questions (1) We have noted in Remark 1 at the end of Section 3 that the basic consensus Algorithms l-3, with minor modifications, have the property that the number of rounds required to reach agreement after round GST is optimal to within constant factors (at most 12). We have not tried to reduce these constants. Some reduction is probably possible, say by overlapping trying phases with lock-release phases, although it would be surprising if the number of rounds could be made to match the known lower bound of t + 1 rounds. On the other hand, partial synchrony might provide a model for which the lower bound t + 1 could be strengthened to something larger. (2) A general direction for future research is to study other distributed computing problems in partially synchronous models. ACKNOWLEDGMENTS. Joe Halpern asked whether the impossibility results of [4] and [lo] would continue to hold in case the parameters + or A exist but are not known a priori, and this led to the formulation of the version of partial synchrony where phi or delta are unknown. We are grateful to Jennifer Lundelius Welch who read a draft of this paper and provided many helpful comments. REFERENCES 1. ATTIYA, A., DOLEV, D., AND GIL, J. Asynchronous Byzantine consensus. In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 119- 133. 2. BRACHA, G., AND TOUEG, S. Asynchronous consensus and broadcast protocols. J. ACM 32, 4 (Oct. 1985), 824-840.