
Why Extension-Based Proofs Fail
Faith Ellen, from the University of Toronto, examines a core proof technique in distributed computing: the valency argument, a type of extension-based proof modeled as an interaction between a prover and a protocol. She shows that although no wait-free algorithm exists to solve 2-set agreement among three processes communicating by read and write, this impossibility result cannot actually be established through an extension-based proof. Ellen works through the structure of such proofs, where they succeed, and why this particular case resists them, then surveys several other known impossibility results in distributed computing that likewise have no extension-based proof. Delivered as part of the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar II, the talk is aimed at an audience already familiar with distributed algorithms and impossibility arguments, and it treats the limits of a standard proof technique as a subject in its own right.