Why extension-based proofs fail
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu · 2019
It is impossible to deterministically solve wait-free consensus in an asynchronous system. The classic proof uses a valency argument, which constructs an infinite execution by repeatedly extending a finite execution. We introduce extension-based proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments.