Test-and-Set in Optimal Space
George Giakkoupis, Maryam Helmi, Lisa Highám, Philipp Woelfel · 2015
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 [12,21] for obstruction-free and deadlock-free implementations, and recently a deterministic obstruction-free implementation using O(√ n) registers was presented [11].