Jimmy Zhu: A Tight Space Bound for Consensus

Monday, February 15, 2016 - 1:00pm to 2:30pm
Jimmy Zhu
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.