Efficient Randomized Test-And-Set Implementations

Abstract : We study randomized test-and-set (TAS) implementations from registers in the asynchronous shared memory model with n processes. We introduce the problem of group election, a natural variant of leader election, and propose a framework for the implementation of TAS objects from group election objects. We then present two group election algorithms, each yielding an efficient TAS implementation. The first implementation has expected max-step complexity O(log* k) in the location-oblivious adversary model, and the second has expected max-step complexity O(log log k) against any read/write-oblivious adversary, where k ≤ n is the contention. These algorithms improve the previous upper bound by Alistarh and Aspnes [2] of O(log log n) expected max-step complexity in the oblivious adversary model. We also propose a modification to a TAS algorithm by Alistarh, Attiya, Gilbert, Giurgiu, and Guerraoui [5] for the strong adaptive adversary, which improves its space complexity from super-linear to linear, while maintaining its O(log n) expected max-step complexity. We then describe how this algorithm can be combined with any randomized TAS algorithm that has expected max-step complexity T(n) in a weaker adversary model, so that the resulting algorithm has O(log n) expected max-step complexity against any strong adaptive adversary and O(T(n)) in the weaker adversary model. Finally, we prove that for any randomized 2-process TAS algorithm, there exists a schedule determined by an oblivious adversary such that with probability at least 1/4^t one of the processes needs at least t steps to finish its TAS operation. This complements a lower bound by Attiya and Censor-Hillel [7] on a similar problem for n ≥ 3 processes.
Document type :
Journal articles
Complete list of metadatas

Contributor : George Giakkoupis <>
Submitted on : Friday, February 8, 2019 - 9:44:00 PM
Last modification on : Wednesday, February 13, 2019 - 1:23:47 AM
Long-term archiving on : Thursday, May 9, 2019 - 4:18:43 PM


Files produced by the author(s)


  • HAL Id : hal-02012672, version 1


George Giakkoupis, Philipp Woelfel. Efficient Randomized Test-And-Set Implementations. Distributed Computing, Springer Verlag, In press. ⟨hal-02012672⟩



Record views


Files downloads