Jimmy Zhu: A Tight Space Bound for Consensus

Abstract: Existing n-process randomized wait-free (and obstruction-free) consensus algorithms from registers all use at least n registers. In 1993, it was proved that such algorithms need to use at least Omega(sqrt(n)) registers. Recently, this was improved to n/20 registers in the anonymous setting, where processes do not have identifiers. Closing the gap in the general case, however, remained an open problem. We resolve this problem by proving that any randomized wait-free (or obstruction-free) consensus algorithm for n processes must use at least n-1 registers.