Paper Info
Title
The correctness proof of Ben-Or's randomized consensus algorithm.
Abstract
In a ground-breaking paper that appeared in 1983, Ben-Or presented the first randomized algorithm to solve consensus in an asynchronous message-passing system where processes can fail by crashing. Although more efficient randomized algorithms were subsequently proposed, Ben-Or’s algorithm is still the simplest and most elegant one. For this reason, it is often taught in distributed computing courses and it appears in several textbooks. Even though Ben-Or’s algorithm is widely known and it is very simple, surprisingly a proof of correctness of the algorithm has not yet appeared: previously published proofs make some simplifying assumptions—specifically, they either assume that < /3 ( is the total number of processes and is maximum number of processes that may crash) or that the adversary is weak, that is, it cannot see the process states or the content of the messages. In this paper, we present a correctness proof for Ben-Or’s randomized consensus algorithm for the case that < /2 process crashes and the adversary is strong (i.e., it can see the process states and message contents, and schedule the process steps and message receipts accordingly). To the best of our knowledge, this is the first full proof of this classical algorithm. We also demonstrate a counterintuitive problem that may occur if one uses the well-known abstraction of a “global coin” to modularize and speed up randomized consensus algorithms, such as Ben-Or’s algorithm. Specifically, we show that contrary to common belief, the use of a global coin can sometimes be deleterious rather than beneficial: instead of speeding up Ben-Or’s algorithm, the use of a global coin in this algorithm may actually prevent termination.
Year
DOI
Venue
2012
https://doi.org/10.1007/s00446-012-0162-z
Correctness Proof of Ben-Or''s Randomized Consensus Algorithm
Keywords
DocType
Volume
Correct Process,Correctness Proof,Consensus Problem,Liveness Property,Consensus Algorithm
Journal
25
Issue
ISSN
Citations 
5
0178-2770
7
PageRank 
References 
Authors
0.45
6
2
Name
Order
Citations
PageRank
Marcos Kawazoe Aguilera12519153.60
Sam Toueg24557541.76