The consensus problem in unreliable distributed systems (a brief survey)

1. Ben-Or, M. “Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols.” Proc. 2nd ACM Symposium on Principles of Distributed Computing, 1983. To appear.

   Google Scholar 

2. Davies, D. and Wakerly, J. F. “Synchronization and Matching in Redundant Systems.” IEEE Trans. on Computers C-27, 6 (June 1978), 531–539.

   Google Scholar 

3. DeMillo, R. A., Lynch, N. A., and Merritt, M. J. “Cryptographic Protocols.” Proc. 14th ACM Symposium on Theory of Computing, 1982, pp. 383–400.

   Google Scholar 

4. Diffie, W. and Hellman, M. “New Directions in Cryptography.” IEEE Trans. on Information Theory IT-22 (1976), 644–654.

   Article  Google Scholar 

5. Dolev, D. “Unanimity in an Unknown and Unreliable Environment.” Proc. 22nd IEEE Symposium on Foundations of Computer Science, 1981, pp. 159–168.

   Google Scholar 

6. Dolev, D. “The Byzantine Generals Strike Again.” J. Algorithms 3, 1 (1982), 14–30.

   Google Scholar 

7. Dolev, D., Dwork, C., and Stockmeyer, L. On the Minimal Synchronism Needed for Distributed Consensus. Manuscript.

   Google Scholar 

8. Dolev, D., Fischer, M. J., Fower, R., Lynch, N. A., and Strong, H. R. “An Efficient Byzantine Agreement Without Authentication.” Information and Control (to appear). See also IBM Research Report RJ3428 (1982).

   Google Scholar 

9. Dolev, D., Lynch, N. A., and Pinter, S. Reaching Approximate Agreement in the Presence of Faults. Manuscript.

   Google Scholar 

10. Dolev, D., and Reischuk, R. “Bounds on Information Exchange for Byzantine Agreement.” Proc. ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 1982, pp. 132–140.

    Google Scholar 

11. Dolev, D., Reischuk, R., and Strong, H. R. “Eventual' is Earlier Than ‘Immediate'.” 23rd IEEE Symposium on Foundations of Computer Science, 1982, pp. 196–203.

    Google Scholar 

12. Dolev, D., and Strong, H. R. “Polynomial Algorithms for Multiple Processor Agremment.” Proc. 14th ACM Symposium on Theory of Computing, 1982, pp. 401–407.

    Google Scholar 

13. Dolev, D., and Strong, H. R. “Distributed Commit with Bounded Waiting.” Proc. Second Symposium on Reliability in Distributed Software and Database System, Pittsburgh, July, 1982.

    Google Scholar 

14. Dolev, D., and Strong, H. R. “Requirements for Agreement in a Distributed System.” Proc. Second International Symposium on Distributed Data Bases, Berlin, Sept., 1982.

    Google Scholar 

15. Dolev, D., and Strong, H. R. “Authenticated Algorithms for Byzantine Agreement.” SIAM J. Comput. (to appear). See also IBM Research Report RJ3416 (1982).

    Google Scholar 

16. Fischer, M. J., Fowler, R. J., and Lynch, N. A. “A Simple and Efficient Byzantine Generals Algorithm.” Proc Second IEEE Symposium on Reliability in Distributed Software and Database Systems, Pittsburgh, 1982, pp. 46–52.

    Google Scholar 

17. Fischer, M. J., and Lynch, N. A. “A Lower Bound for the Time to Assure Interactive Consistency.” Inf. Proc. Lett. 14, 4 (1982), 183–186.

    Google Scholar 

18. Fischer, M. J., Lynch, N. A., and Paterson, M. S. “Impossibility of Distributed Consensus with One Faulty Process.” Proc. Second ACM Symposium on Principles of Database Systems, March, 1983.

    Google Scholar 

19. Gifford, D. K. Weighted Voting for Replicated Data. Tech. Rept. CSL-79-14, XEROX Palo Alto Research Center, Sept., 1979.

    Google Scholar 

20. Gray, J. A Discussion of Distributed Systems. Research Report RJ2699, IBM, Sept., 1979.

    Google Scholar 

21. Lamport, L. “Using Time Instead of Timeout for Fault-Tolerant Distributed Systems.” ACM Trans. on Programming Lang. and Systems (to appear). See also technical report, Computer Science Laboratory, SRI International (June 1981).

    Google Scholar 

22. Lamport, L. “The Weak Byzantine Generals Problem.” J. ACM 30, 3 (July 1983). To appear.

    Google Scholar 

23. Lamport, L. and Fischer, M. J. Byzantine Generals and Transaction Commit Protocols. Manuscript.

    Google Scholar 

24. Lamport, L., and Melliar-Smith, P.M. Synchronizing Clocks in the Presence of Faults. Computer Science Laboratory, SRI International, March, 1982.

    Google Scholar 

25. Lamport, L., Shostak, R., and Pease, M. “The Byzantine Generals Problem.” ACM Trans. on Programming Lang. and Systems 4, 3 (July 1982), 382–401.

    Google Scholar 

26. Lindsay, B. G., et al. Notes on Distributed Databases. Research Report RJ2571, IBM, July, 1979.

    Google Scholar 

27. Merritt, M. J. Cryptographic Protocols. Tech. Rept. GIT-ICS-83/06, School of Inf. & Comp. Sci., Georgia Institute of Technology, Feb., 1983.

    Google Scholar 

28. Mohan, C., Strong, H. R., and Finkelstein, S. Method for Distributed Transaction Commit and Recovery Using Byzantine Agreement within Clusters of Processors. Research Report RJ3882, IBM, 1983.

    Google Scholar 

29. Pease, M., Shostak, R., and Lamport, L. “Reaching Agreement in the Presence of Faults.” J. ACM 27, 2 (1980), 228–234.

    Google Scholar 

30. Popek, G., et al. “LOCUS: A Network Transparent, High Reliability Distributed System.” Proc. 8th ACM Symposium on Operating Systems Principles, Dec., 1981, pp. 169–177.

    Google Scholar 

31. Rabin, M. Randomized Byzantine Generals. Manuscript.

    Google Scholar 

32. Reischuk, R. A New Solution for the Byzantine Generals Problem. Research Report RJ3673, IBM, Nov., 1982.

    Google Scholar 

33. Rivest, R., Shamir, A., and Adleman, L. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” Comm. ACM 21, 2 (Feb. 1978), 120–126.

    Article  Google Scholar 

34. Schneider, F. B., Gries, D., and Schlichting, R. D. Fast Reliable Broadcasts. Computer Science Technical Report TR 82-519, Cornell University, Sept., 1982.

    Google Scholar 

35. Wensley, J. H., et al. “SIFT: Design and Analysis of a Fault-Tolerant Computer for Aircraft Control.” Proc. IEEE 66, 10 (Oct. 1978), 1240–1255.

    Google Scholar 

Download references