The space complexity of consensus from swap

DOI10.1145/3631390MaRDI QIDQ7031996zbMATH OpenFDO

Authors Sean Ovens

Publication date 5 February 2025

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3631390

zbMATH Keywords

consensuslower boundsset agreementshared memoryspace complexity

Mathematics Subject Classification ID

Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Cites work

• A complexity-based classification for multiprocessor synchronization
• A tight space bound for consensus
• Anonymous obstruction-free (n,k)-set agreement with n-k+1 atomic read/write registers
• Atomic snapshots of shared memory
• Bounds on shared memory for mutual exclusion
• Composite registers
• Fast randomized consensus using shared memory
• Generalized FLP impossibility result for t-resilient asynchronous computations
• 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
• On the space complexity of randomized synchronization
• On the space complexity of set agreement?
• Revisionist simulations: a new approach to proving space lower bounds
• The Space Complexity of Consensus from Swap
• The Space Complexity of Scannable Binary Objects
• The topological structure of asynchronous computability
• Time lower bounds for implementations of multi-writer snapshots
• Understanding the set consensus partial order using the Borowsky-Gafni simulation (extended abstract)
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge

This page was built for publication: The space complexity of consensus from swap

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