A TIGHT SPACE BOUND FOR CONSENSUS.

In the consensus problem, there are n processes that each has a private input value. Each nonfaulty process must output a single value such that no two processes output different values and the output is the input value of some process. There are many consensus protocols for systems where the processes may only communicate by reading and writing to shared registers. Of particular interest are protocols that have progress guarantees such as randomized wait-freedom or obstructionfreedom. In 1992, it was proved that such protocols must use Ω(√n) registers. In 2015, this was improved to Ω(n) registers in the anonymous setting, where processes do not have identifiers. We prove that every randomized wait-free or obstruction-free protocol for solving consensus among n processes must use at least n - 1 registers. [ABSTRACT FROM AUTHOR]