An O(sqrt(n)) space bound for obstruction-free leader election

Abstract : We present a deterministic obstruction-free implementation of leader election from $O(\sqrt n)$ atomic $O(\log n)$-bit registers in the standard asynchronous shared memory system with $n$ processes. We provide also a technique to transform any deterministic obstruction-free algorithm, in which any process can finish if it runs for $b$ steps without interference, into a randomized wait-free algorithm for the oblivious adversary, in which the expected step complexity is polynomial in $n$ and $b$. This transformation allows us to combine our obstruction-free algorithm with the leader election algorithm by Giakkoupis and Woelfel (2012), to obtain a fast randomized leader election (and thus test-and-set) implementation from $O(\sqrt n)$ $O(\log n)$-bit registers, that has expected step complexity $O(\log^\ast n)$ against the oblivious adversary. Our algorithm provides the first sub-linear space upper bound for obstruction-free leader election. A lower bound of $\Omega(\log n)$ has been known since 1989. Our research is also motivated by the long-standing open problem whether there is an obstruction-free consensus algorithm which uses fewer than $n$ registers.
Type de document :
Communication dans un congrès
DISC - 27th International Symposium on Distributed Computing, Oct 2013, Jerusalem, Israel. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00875167
Contributeur : George Giakkoupis <>
Soumis le : lundi 21 octobre 2013 - 12:31:10
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : mercredi 22 janvier 2014 - 04:26:26

Fichier

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

Identifiants

  • HAL Id : hal-00875167, version 1

Citation

George Giakkoupis, Maryam Helmi, Lisa Higham, Philipp Woelfel. An O(sqrt(n)) space bound for obstruction-free leader election. DISC - 27th International Symposium on Distributed Computing, Oct 2013, Jerusalem, Israel. 2013. 〈hal-00875167〉

Partager

Métriques

Consultations de la notice

530

Téléchargements de fichiers

468