Brief announcement: A tight space bound for consensus

DOI10.1145/2933057.2933078MaRDI QIDQ5361929zbMATH OpenOpenAlexFDO

Authors Leqi Zhu

Publication date 29 September 2017

Published in Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

consensusshared memoryspace complexity

Mathematics Subject Classification ID

Network protocols (68M12) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A tight space bound for consensus
• A tight space bound for consensus
• Randomized consensus in expected \(O(n ^{2})\) total work using single-writer registers

Cited in

(4)

• A tight space bound for consensus
• Revisionist simulations: a new approach to proving space lower bounds
• A tight space bound for consensus
• The Space Complexity of Consensus from Swap

This page was built for publication: Brief announcement: A tight space bound for consensus

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