Bounded polynomial randomized consensus
Hagit Attiya, Danny Dolev, Nir Shavit · 1989
In [A&3], Abrahamson presented a solution to the randomized consensus problem of Chor, Israeli and Li [CIL87], without assuming the existence of an atomic coin flip operation.This elegant algorithm uses unbounded memory, and has expected exponential running time.In [AH89], Aspens and Herlihy provide a breakthrough polynomial-time algorithm.However, it too is based on the use of unbounded memory.In this paper, we present a solution to the randomized consensus problem, that is bounded in space and runs in polynomial expected time.