Why Extension-Based Proofs Fail

DOI10.1137/20M1375851MaRDI QIDQ6115415zbMATH OpenFDO

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

Publication date 10 August 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/20M1375851

zbMATH Keywords

impossibility proofsset agreementvalency arguments

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites work

• A layered analysis of consensus
• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• An axiomatic approach to computing the connectivity of synchronous and asynchronous systems
• An overview of synchronous message-passing and topology
• Atomic snapshots of shared memory
• Brief Announcement: Why Extension-Based Proofs Fail
• Counting-based impossibility proofs for renaming and set agreement
• Exponential lower bounds for the pigeonhole principle
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Hardness of Distributed Optimization
• Immediate atomic snapshots and fast renaming
• Impossibility of distributed consensus with one faulty process
• Impossibility results for distributed computing
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• New combinatorial topology bounds for renaming: the lower bound
• Revisionist simulations: a new approach to proving space lower bounds
• The Combinatorial Structure of Wait-Free Solvable Tasks
• The topological structure of asynchronous computability
• Tight bounds for k-set agreement
• Toward a Topological Characterization of Asynchronous Complexity
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Wait-free approximate agreement on graphs
• Why extension-based proofs fail

Cited in

(1)

• Defining logical obstruction with fixpoints in epistemic logic

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 Q6115415)