Correctness Proof of Ben-Or's Randomized Consensus Algorithm
Aguilera, Marcos Kawazoe; Toueg, Sam
We present a correctness proof for Ben-Or's Randomized Consensus Algorithm for the case in which processes can fail by crashing, and a majority of processes is correct. This is the first time that the proof of Ben-Or's algorithm appears for this case. The proof has been extracted from [AT96]: it is a simplification of the correctness proof of a more complex consensus algorithm that involves both randomization and failure detection.
computer science; technical report
Previously Published As