# On the time and space complexity of randomized test-and-set

1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : We study the time and space complexity of randomized Test-And-Set (TAS) implementations from atomic read/write registers in asynchronous shared memory models with $n$ processes. We present an adaptive TAS algorithm with an expected (individual) step complexity of $O(\log^\ast k)$, for contention $k$, against the oblivious adversary, improving a previous (non-adaptive) upper bound of $O(\log\log n)$ (Alistarh and Aspnes, 2011). We also present a modified version of the adaptive RatRace TAS algorithm (Alistarh et al., 2010), which improves the space complexity from $O(n^3)$ to $O(n)$, while maintaining logarithmic expected step complexity against the adaptive adversary. We complement this upper bound with an $\Omega(\log n)$ lower bound on the space complexity of any TAS algorithm that has the nondeterministic solo-termination property (which is a weaker progress condition than wait-freedom). No non-trivial lower bounds on the space requirements of TAS were known prior to this work.
Type de document :
Communication dans un congrès
PODC - 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Jul 2012, Madeira, Portugal. 2012

Littérature citée [14 références]

https://hal.inria.fr/hal-00722947
Contributeur : George Giakkoupis <>
Soumis le : lundi 6 août 2012 - 17:07:44
Dernière modification le : vendredi 16 novembre 2018 - 01:39:03
Document(s) archivé(s) le : mercredi 7 novembre 2012 - 03:22:53

### Fichier

podc2012_tas.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-00722947, version 1

### Citation

George Giakkoupis, Philipp Woelfel. On the time and space complexity of randomized test-and-set. PODC - 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Jul 2012, Madeira, Portugal. 2012. 〈hal-00722947〉

### Métriques

Consultations de la notice

## 452

Téléchargements de fichiers