Why extension-based proofs fail

Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. Why extension-based proofs fail. Submitted to STOC 2019.


We prove that a class of fundamental shared memory tasks are not amenable to certain standard proof techniques in the field. We formally define a class of extension-based proofs, which contains impossibility arguments like the valency proof by Fisher, Lynch and Patterson of the impossibility of wait-free consensus in an asynchronous system. We introduce a framework which models such proofs as an interaction between a prover and an adversarial protocol. Our main contribution is showing that extension-based proofs are inherently limited in power: for instance, they cannot establish the impossibility of solving (n−1)-set agreement among n≥3 processes in a wait-free manner. This impossibility result does have proofs which are not extension-based: they rely, either explicitly or implicitly, on combinatorial topology. However, it was unknown whether proofs based on simpler techniques were possible.


author    = {Alistarh, Dan and Aspnes, James and Ellen, Faith and Gelashvili, Rati and Zhu, Leqi},
title     = {Why extension-based proofs fail},
  month = nov,
  year = 2018,
  note={Submitted to STOC 2019}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page