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 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 nonconstructive arguments. We define the 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 work is joint with Dan Alistarh, James Aspnes, Rati Gelashvili, and Leqi Zhu and appeared at STOC 2019.
Bio: Faith Ellen received her Ph.D. from the University of California, Berkeley, in 1982, became a faculty member at the University of Washington in 1983, and moved to the University of Toronto in 1986, where she is a Professor of Computer Science. She was the program committee chair for DISC 2002, OPODIS 2018, and PODC 2019, served as the chair of the PODC steering committee from 2006 to 2009, and was vice-president of SIGACT from 1997 to 2001. Her research interests include the theory of distributed computing, data structures, and complexity and she is a co-author of the book “Impossibility Results for Distributed Computing”. Faith became a Fellow of the Association for Computing Machinery in 2014. She is visiting IST Austria until the end of April.
