--- res: bibo_abstract: - "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.\r\n\r\nUsing proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Dan-Adrian foaf_name: Alistarh, Dan-Adrian foaf_surname: Alistarh foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0003-3650-940X - foaf_Person: foaf_givenName: James foaf_name: Aspnes, James foaf_surname: Aspnes - foaf_Person: foaf_givenName: Faith foaf_name: Ellen, Faith foaf_surname: Ellen - foaf_Person: foaf_givenName: Rati foaf_name: Gelashvili, Rati foaf_surname: Gelashvili - foaf_Person: foaf_givenName: Leqi foaf_name: Zhu, Leqi foaf_surname: Zhu bibo_doi: 10.1145/3313276.3316407 dct_date: 2019^xs_gYear dct_identifier: - UT:000523199100089 dct_isPartOf: - http://id.crossref.org/issn/9781450367059 dct_language: eng dct_publisher: ACM Press@ dct_title: Why extension-based proofs fail@ ...