Extension-Based Proofs for Synchronous Message Passing
Date:
There is no wait-free algorithm that solves $k$-set agreement among $n ≥ k + 1$ processes in asynchronous systems where processes communicate using only registers. However, proofs of this result for $k \geq 2$ are complicated and involve topological reasoning. To explain why such sophisticated arguments are necessary, Alistarh, Aspnes, Ellen, Gelashvili, and Zhu recently introduced extension based proofs, which generalize valency arguments, and proved that there are no extension-based proofs of this result.
In the synchronous message passing model, $k$-set agreement is solvable, but there is a lower bound of $t$ rounds for any $k$-set agreement algorithm among $n > kt$ processes when at most $k$ processes can crash each round. The proof of this result for $k \geq 2$ is also a complicated topological argument. We define a notion of extension-based proofs for this model and we show there are no extension-based proofs that $t$ rounds are necessary for any k-set agreement algorithm among $n = kt + 1$ processes, for $k \geq 2$ and $t > 2$, when at most $k$ processes can crash each round. In particular, our result shows that no valency argument can prove this lower bound