Theory Seminar

Why Extension-based Proofs Fail

Rati Gelashvili

Friday, October 12, 2018
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

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.

Additional Information

Sponsor(s): Theory Group

Faculty Sponsor: Seth Pettie

Open to: Public