Consensus in the Presence of Partial Synchrony 323 3. DOLEV, D., AND STRONG, H. R. Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12 (1983), 656-666. 4. DOLEV, D., DWORK, C., AND STOCKMEYER, L. On the minimal synchronism needed for distributed consensus. J. ACM34, 1 (Jan. 1987), 77-97. 5. DOLEV, D., FISCHER, M. J., FOWLER, R., LYNCH, N. A., AND STRONG, H. R. Efficient Byzantine agreement without authentication. I& Control 52 (1982), 257-274. 6. DOLEV, D., LYNCH, N. A., PINTER, S. S., STARK, E. W., AND WEIHL, W. E. Reaching approximate agreement in the presence of faults. J. ACM 33, 3 (July 1986), 499-5 16. 7. DWORK, C., AND Mosm, Y. Knowledge and common knowledge in a Byzantine environment I: Crash failures. In Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning about Knowledge (Monterey, Calif., Mar. 19-22). Kaufmann, Los Altos, Calif., 1986, pp. 149-169. 8. FISCHER, M. J. The consensus problem in unreliable distributed systems (a brief survey). Rep. YALEU/DSC/RR-273. Dept. of Computer Science, Yale Univ., New Haven, Conn., June 1983. 9. FISCHER, M. J., AND LAMPORT, L. Byzantine generals and transaction commit protocols. Tech. Rep. Gp. 62, SRI International, Menlo Park, Calif., 1982. 10. FISCHER, M. J., LYNCH, N. A., AND PATERSON, M. S. Impossibility of distributed consensus with one faulty process. J. ACM 32,2 (Apr. 1985), 374-382. 11. GARCIA-M• LINA, H., P~T~ELLI, F., AND DAVIDSON, S. Is Byzantine agreement useful in a distrib- uted database? In Proceedings of the 3rd SIGACT-SIGMOD Symposium on Principles of Database Systems (Waterloo, Ont., Canada, Apr. 2-4). ACM, New York, 1984, pp. 6 l-69. 12. GRAY, J. N. Notes on database operating systems. In Operating Systems: An Advanced Course. Lecture Notes in Computer Science, vol. 60. Springer-Verlag, New York, 1978, pp. 393-481. 13. LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565. 14. LAMPORT, L. The weak Byzantine generals problem. J. ACM 30, 3 (July 1983), 668-676. 15. LAMPORT, L., SHOSTAK, R., AND PEASE, M. The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 382-401. 16. PINTER, S. Distributed computation systems: Modelling, verification and algorithms. Ph.D. dis- sertation. Dept. of Computer Science, Boston Univ., Boston, Mass., 1984. 17. REISCHUK, R. A new solution for the Byzantine generals problem. ZnJ Control 64 (1985), 23-42. 18. SCHNEIDER, F. B. Byzantine generals in action: Implementing fail-stop processors. ACM Trans. Comput. Syst. 2, 2 (May 1984), 145-154. 19. SKEEN, D. A quorum based commit protocol. Tech. Rep. TR 82-483, Computer Science Dept., Cornell Univ., Ithaca, N.Y., Feb. 1982. 20. SRIKANTH, T. K., AND TOUEC, S. Simulating authenticated broadcasts to derive simple fault- tolerant algorithms. Rep. 84-623, Computer Science Dept., Cornell Univ., Ithaca, N.Y., 1984. RECEIVED OCTOBER 1985; REVISED JULY 1986 AND MARCH 1987; ACCEPTED MARCH 1987 Journal of the Association for Computing Machinery, Vol. 35, No. 2, April 1988.