Journal of the ACM Bibliography

Categories and Subject Descriptors: C.2.4 [Computer-Communication Networks]: Distributed Systems -- distributed applications, distributed databases, network operating systems; C.4 [Performance of Systems]; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- parallelism; H.2.4 [Database Management]: Systems -- distributed systems

General Terms: Algorithms, Reliability, Theory, Verification

Additional Key Words and Phrases: Agreement problem, asynchronous system, Byzantine Generals problem, commit problem, consensus problem, distributed computing, early stopping, fault tolerance, reliability

Selected papers that cite this one

• James Aspnes and Orli Waarts. Modular competitiveness for distributed algorithms. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 237-246, Philadelphia, Pennsylvania, 22-24 May 1996.

• Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. Journal of the ACM, 41(1):122-152, January 1994.

• Amotz Bar-Noy, Danny Dolev, Cynthia Dwork, and H. Raymond Strong. Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement. Information and Computation, 97(2):205-233, April 1992.

• Amotz Bar-Noy, Xiaotie Deng, Juan A. Garay, and Tiko Kameda. Optimal amortized distributed consensus. Information and Computation, 120(1):93-100, July 1995.

• R. A. Bazzi and G. Neiger. The complexity of almost-optimal simultaneous coordination. Algorithmica, 17(3):308-321, March 1997.

• Brian A. Coan and Jennifer L. Welch. Modular construction of a Byzantine agreement protocol with optimal message bit complexity. Information and Computation, 97(1):61-85, March 1992.

• Pallab Dasgupta. Agreement under faulty interfaces. Information Processing Letters, 65(3):125-129, 13 February 1998.

• Cynthia Dwork, Joseph Y. Halpern, and Orli Waarts. Performing work efficiently in the presence of faults. SIAM Journal on Computing, 27(5):1457-1491, October 1998.

• Juan A. Garay and Yoram Moses. Fully polynomial Byzantine agreement for n > 3t processors in t + 1 rounds. SIAM Journal on Computing, 27(1):247-290, February 1998.

• Prasad Jayanti, Tushar Deepak Chandra, and Sam Toueg. Fault-tolerant wait-free shared objects. Journal of the ACM, 45(3):451-500, May 1998.

Selected references

• Richard A. DeMillo, Nancy A. Lynch, and Michael J. Merritt. Cryptographic protocols. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 383-400, San Francisco, California, 5-7 May 1982.

• D. Dolev. Unanimity in an unknown and unreliable environment. In 22nd Annual Symposium on Foundations of Computer Science, pages 159-168, Nashville, Tennessee, 28-30 October 1981. IEEE.

• Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and H. Raymond Strong. An efficient algorithm for Byzantine agreement without authentication. Information and Control, 52(3):257-274, March 1982.

• Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for Byzantine agreement. Journal of the ACM, 32(1):191-204, January 1985.

• Danny Dolev, Ruediger Reischuk, and H. Raymond Strong. `Eventual' is earlier than `immediate'. In 23rd Annual Symposium on Foundations of Computer Science, pages 196-203, Chicago, Illinois, 3-5 November 1982. IEEE.

• Danny Dolev and H. Raymond Strong. Polynomial algorithms for multiple processor agreement. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 401-407, San Francisco, California, 5-7 May 1982.

• L. Lamport. The weak Byzantine generals problem. Journal of the ACM, 30(3):668-676, July 1983.

• Leslie Lamport and P. M. Melliar-Smith. Synchronizing clocks in the presence of faults. Journal of the ACM, 32(1):52-78, January 1985.

• Yoram Moses and Orli Waarts. Coordinated traversal: (t + 1)-round Byzantine agreement in polynomial time. In 29th Annual Symposium on Foundations of Computer Science, pages 246-255, White Plains, New York, 24-26 October 1988. IEEE.

• M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, April 1980.

Shortcuts: