Simultaneity is harder than agreement

DOI10.1016/0890-5401(91)90067-CzbMATH Open0723.68014OpenAlexW2010212712MaRDI QIDQ757014FDOQ757014

Authors: Brian A. Coan, Cynthia Dwork 

Publication date: 1991

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90067-c

Recommendations

• Bounds on the time to reach agreement in the presence of timing uncertainty
• Common knowledge and consistent simultaneous coordination
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• The Distributed Firing Squad Problem
• No Double Discount: Condition-Based Simultaneity Yields Limited Gain

zbMATH Keywords

lower bounddistributed systemsprotocoldistributed firing squadsimultaneous agreement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)

Cites Work

• Authenticated Algorithms for Byzantine Agreement
• Early stopping in Byzantine agreement
• The Byzantine Generals Problem
• Knowledge and common knowledge in a distributed environment
• A lower bound for the time to assure interactive consistency
• Programming simultaneous actions using common knowledge
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• An O (log n ) expected rounds randomized byzantine generals protocol
• The Distributed Firing Squad Problem
• Flipping Persuasively in Constant Time
• Simple constant-time consensus protocols in realistic failure models
• Coordinated Traversal: (t + 1)-Round Byzantine Agreement in Polynomial Time
• Simultaneity is harder than agreement

Cited In (6)

• The curse of simultaneity
• Hundreds of impossibility results for distributed computing
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Simultaneity is harder than agreement
• Near-optimal self-stabilising counting and firing squads
• The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols

This page was built for publication: Simultaneity is harder than agreement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757014)