Why Extension-Based Proofs Fail

DOI10.1137/20m1375851MaRDI QIDQ6115415

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

Publication date: 10 August 2023

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

zbMATH Keywords

set agreementimpossibility proofsvalency arguments

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Exponential lower bounds for the pigeonhole principle
• New combinatorial topology bounds for renaming: the lower bound
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• A Layered Analysis of Consensus
• An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems
• Tight bounds for k -set agreement
• The Combinatorial Structure of Wait-Free Solvable Tasks
• The topological structure of asynchronous computability
• Toward a Topological Characterization of Asynchronous Complexity
• Impossibility of distributed consensus with one faulty process
• Atomic snapshots of shared memory
• Impossibility Results for Distributed Computing
• Counting-Based Impossibility Proofs for Renaming and Set Agreement
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Hardness of Distributed Optimization
• Revisionist Simulations
• Why extension-based proofs fail
• Generalized FLP impossibility result for t-resilient asynchronous computations
• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• Immediate atomic snapshots and fast renaming
• Brief Announcement: Why Extension-Based Proofs Fail
• Wait-free approximate agreement on graphs