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 obstruction-freedom. In 1992, it was proved that such protocols must use Omega(root n) registers. In 2015, this was improved to Omega(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.

Automated summary

In the consensus problem, protocols must ensure that all processes output the same value, which is the input value of one of the processes. Protocols with progress guarantees must use at least n-1 registers.