Tight bounds for asynchronous randomized consensus

A distributed consensus algorithm allows n processes to reach acommon decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in anasynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminatewith probability 1. Randomized consensus algorithms are typically evaluated by their total step complexity, which is the expected total number of steps taken by all processes.

Authors

• Hagit Attiya
• Keren Censor-Hillel

Keywords

• distributed computing
• lower bound
• shared-memory
• isoperimetric inequality
• randomized algorithms