🚀 go-pugleaf

           Department of Computer Science, University of Toronto
         (SF = Sandford Fleming Building, 10 King's College Road)

       -------------------------------------------------------------

                                  THEORY
                   SF1105, at 3:00 p.m., 1 October 1992

                               Faith E. Fich
           Department of Computer Science, University of Toronto

                        "A Lower Bound on the Space
               Complexity of Randomized Wait-free Consensus"

Herlihy proved that, with atomic read/write registers, even two processes
cannot achieve wait-free consensus using a deterministic algorithm.
However, using randomization, $n$ processes can achieve wait-free
consensus.  In this talk, I will prove that $Omega(rt n)$ atomic read/write
registers (of unbounded size) are necessary to solve $n$-process consensus.
This is the only lower bound for randomized wait-free computation that is
known.

This work is joint with Maurice Herlihy and Nir Shavit.