On the optimal space complexity of consensus for anonymous processes

DOI10.1007/s00446-018-0331-9zbMath1451.68044arXiv1506.06817OpenAlexW2789457537WikidataQ130071304 ScholiaQ130071304MaRDI QIDQ5915696

Rati Gelashvili

Publication date: 13 August 2018

Published in: Lecture Notes in Computer Science, Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.06817

zbMATH Keywords

consensusspace complexityregistersanonymous processes

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)

Related Items (5)

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 ⋮ Allocate-On-Use Space Complexity of Shared-Memory Algorithms ⋮ A Tight Space Bound for Consensus

Cites Work

• Unnamed Item
• Unnamed Item
• Test-and-Set in Optimal Space
• On the space complexity of randomized synchronization
• Fast randomized consensus using shared memory
• Impossibility of distributed consensus with one faulty process
• Impossibility Results for Distributed Computing
• A tight space bound for consensus
• Distributed Computing

This page was built for publication: On the optimal space complexity of consensus for anonymous processes