Simultaneity is harder than agreement

DOI10.1016/0890-5401(91)90067-CMaRDI QIDQ757014zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

distributed firing squaddistributed systemslower boundprotocolsimultaneous agreement

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(11)

• A tradeoff between safety and liveness for randomized coordinated attack
• Message lower bounds via efficient network synchronization
• The curse of simultaneity
• Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions
• Hundreds of impossibility results for distributed computing
• A tradeoff between safety and liveness for randomized coordinated attack protocols
• Near-optimal self-stabilising counting and firing squads
• Tight bounds on the round complexity of distributed 1-solvable tasks
• Simultaneity is harder than agreement
• The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols
• Knowledge and common knowledge in a Byzantine environment: Crash failures

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)