A simple proof of the uniform consensus synchronous lower bound.

DOI10.1016/S0020-0190(02)00333-2zbMath1042.68010OpenAlexW2101712143MaRDI QIDQ1853174

Sergio Rajsbaum, Idit Keidar

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00333-2

zbMATH Keywords

Distributed computingFault toleranceLower boundsConsensus

Mathematics Subject Classification ID

Distributed systems (68M14)

Related Items (12)

Unbeatable consensus ⋮ Synchronous condition-based consensus ⋮ Fast non-blocking atomic commit: an inherent trade-off ⋮ Self-stabilizing indulgent zero-degrading binary consensus ⋮ Message and time efficient consensus protocols for synchronous distributed systems ⋮ The inherent price of indulgence ⋮ The overhead of consensus failure recovery ⋮ Multi-shot distributed transaction commit ⋮ Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures ⋮ Unnamed Item ⋮ Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound ⋮ A bivalency proof of the lower bound for uniform consensus

Cites Work

• Unnamed Item
• Unnamed Item
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• A simple bivalency proof that \(t\)-resilient consensus requires \(t+1\) rounds
• A Layered Analysis of Consensus
• Early stopping in Byzantine agreement
• Impossibility of distributed consensus with one faulty process
• Early consensus in an asynchronous system with a weak failure detector
• Indulgent algorithms (preliminary version)

This page was built for publication: A simple proof of the uniform consensus synchronous lower bound.