Test-and-Set in Optimal Space

DOI10.1145/2746539.2746627zbMath1321.68105OpenAlexW1984077287MaRDI QIDQ2941557

George Giakkoupis, Maryam Helmi, Philipp Woelfel, Lisa Higham

Publication date: 21 August 2015

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

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

zbMATH Keywords

space complexityobstruction-freeshared memory modeltest-and-set algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items

Efficient randomized test-and-set implementations ⋮ On the optimal space complexity of consensus for anonymous processes ⋮ A Tight Space Bound for Consensus

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming