Why Extension-Based Proofs Fail
From MaRDI portal
Publication:6115415
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)
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
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