Why extension-based proofs fail

DOI10.1145/3313276.3316407MaRDI QIDQ5212839zbMATH OpenOpenAlexFDO

Authors Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.01421

zbMATH Keywords

combinatorial topologyimpossibility proofsset agreementvalency arguments

Mathematics Subject Classification ID

Distributed systems (68M14) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k > 1 processes in a wait-free manner in certain asynchronous models. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained for one of these models by an extension-based proof and, hence, extension-based proofs are limited in power.

Recommendations

• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Impossibility of distributed consensus with one faulty process
• A non-topological proof for the impossibility of \(k\)-set agreement
• Counting-based impossibility proofs for renaming and set agreement
• A constructive proof for FLP

Cited in

(7)

• Wait-free approximate agreement on graphs
• A topological perspective on distributed network algorithms
• Wait-free approximate agreement on graphs
• Why Extension-Based Proofs Fail
• A topological view of partitioning arguments: reducing k-set agreement to consensus
• Locally solvable tasks and the limitations of valency arguments
• Satrapy: from abstract to practical consensus for heterogeneous quorum systems

This page was built for publication: Why extension-based proofs fail

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212839)