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" .
Type de document :
Communication dans un congrès
47th Annual ACM Symposium on Theory of Computing (STOC 2015), Jun 2015, Portland, OR, United States. pp. 615-623, 〈10.1145/2746539.2746627〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01250520
Contributeur : George Giakkoupis <>
Soumis le : mercredi 6 janvier 2016 - 11:50:06
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : jeudi 7 avril 2016 - 15:47:53

Fichier

stoc15tas-space.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

252

Téléchargements de fichiers

77