Why Extension-based Proofs Fail

It is impossible to solve consensus without using locks or randomization in an asynchronous system where 2 processes communicate by reading from and writing to shared memory. The celebrated proof of this claim by Fischer, Lynch and Paterson builds an infinite execution, by repeatedly extending a finite execution, in which no process decides a value. In contrast, all known proofs of the impossibility of solving (n-1)-set agreement among n ‰¥ 3 processes rely on complex topological arguments, either directly or indirectly. (n-1)-set agreement requires n processes to decide at most n-1 different values and is equivalent to consensus when n=2.

We define a class of extension-based proofs and show that no such proof can prove the unsolvability of (n-1)-set agreement among n ‰¥ 3 processes. To do so, we view a proof as an interaction between a prover, who is trying to construct a bad execution (in which n values are decided or some process takes an infinite number of steps without deciding a value), and an adversarial algorithm which is constructed adaptively. This, for the first time, sheds some light on why the conventional techniques have spectacularly failed for n>2.

I will also show how intuitions derived from this work can guide us in proving the first strong space lower bound for solving k-set agreement among n processes. Our proof algorithmically reduces the problem to the aforementioned impossibility result, hence indirectly relying on a topological argument to make the leap.

This is based on joint works with Dan Alistarh, James Aspnes, Faith Ellen, and Leqi Zhu.