Skip to Main content Skip to Navigation
Conference papers

Test-and-Set in Optimal Space

Abstract : The test-and-set object is a fundamental synchronization primitive for shared memory systems. This paper addresses the number of registers (supporting atomic reads and writes) required to implement a one-shot test-and-set object in the standard asynchronous shared memory model with n processes. The best lower bound is log n − 1 for obstruction-free and deadlock-free implementations, and recently a deterministic obstruction-free implementation using O(√ n) registers was presented. This paper closes the gap between these existing upper and lower bounds by presenting a deterministic obstruction-free implementation of a one-shot test-and-set object from Θ(log n) registers of size Θ(log n) bits. Combining our obstruction-free algorithm with techniques from previous research, we also obtain a randomized wait-free test-and-set algorithm from Θ(log n) registers, with expected step-complexity Θ(log* n) against the oblivious adversary. The core tool in our algorithm is the implementation of a deterministic obstruction-free sifter object, using only 6 registers. If k processes access a sifter, then when they have terminated, at least one and at most (2k + 1)/3 processes return "win" and all others return "lose" .
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01250520
Contributor : George Giakkoupis <>
Submitted on : Wednesday, January 6, 2016 - 11:50:06 AM
Last modification on : Thursday, January 7, 2021 - 4:20:40 PM
Long-term archiving on: : Thursday, April 7, 2016 - 3:47:53 PM

File

stoc15tas-space.pdf
Files produced by the author(s)

Identifiers

Citation

George Giakkoupis, Maryam Helmi, Lisa Higham, Philipp Woelfel. Test-and-Set in Optimal Space. 47th Annual ACM Symposium on Theory of Computing (STOC 2015), Jun 2015, Portland, OR, United States. pp. 615-623, ⟨10.1145/2746539.2746627⟩. ⟨hal-01250520⟩

Share

Metrics

Record views

462

Files downloads

461