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 agreement; impossibility proofs; valency arguments

Mathematics Subject Classification ID

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