A tight space bound for consensus

DOI10.1145/2897518.2897565zbMath1373.68128OpenAlexW2417507107MaRDI QIDQ5361842

Leqi Zhu

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

consensusspace complexityobstruction-freeshared memory modelrandomized wait-free

Mathematics Subject Classification ID

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

Related Items (6)

Progress-Space Tradeoffs in Single-Writer Memory Implementations ⋮ On the uncontended complexity of anonymous agreement ⋮ Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers ⋮ A complexity-based classification for multiprocessor synchronization ⋮ On the optimal space complexity of consensus for anonymous processes ⋮ Allocate-On-Use Space Complexity of Shared-Memory Algorithms

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