Abstract
It is impossible to solve consensus without using locks in an asynchronous system where 2 processes communicate by reading from and writing to shared registers. The proof of this result, described in my boot camp lecture, 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. 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 is joint work with Dan Alistarh, James Aspnes, Rati Gelashvili, and Leqi Zhu.