Gossip protocols for renaming and sorting

Abstract : We devise efficient gossip-based protocols for some fundamental distributed tasks. The protocols assume an $n$-node network supporting point-to-point communication, and in every round, each node exchanges information of size $O(\log n)$ bits with (at most) one other node. We first consider the \emph{renaming} problem, that is, to assign distinct IDs from a small ID space to all nodes of the network. We propose a renaming protocol that divides the ID space among nodes using a natural push or pull approach, achieving logarithmic round complexity with ID space $\{1,\dots,(1+\epsilon) n\}$, for any fixed $\epsilon >0$. A variant of this protocol solves the \emph{tight} renaming problem, where each node obtains a unique ID in $\{1,\dots,n\}$, in $O(\log^2 n)$ rounds. Next we study the following \emph{sorting} problem. Nodes have consecutive IDs 1 up to $n$, and they receive numerical values as inputs. They then have to exchange those inputs so that in the end the input of rank $k$ is located at the node with ID $k$. Jelasity and Kermarrec (2006) suggested a simple and natural protocol, where nodes exchange values with peers chosen uniformly at random, but it is not hard to see that this protocol requires $\Omega(n)$ rounds. We prove that the same protocol works in $O(\log^2 n)$ rounds if peers are chosen according to a non-uniform power law distribution.
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 [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00875162
Contributeur : George Giakkoupis <>
Soumis le : lundi 21 octobre 2013 - 12:20:24
Dernière modification le : mercredi 11 avril 2018 - 01:51:18
Document(s) archivé(s) le : mercredi 22 janvier 2014 - 04:26:18

Fichier

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

Identifiants

  • HAL Id : hal-00875162, version 1

Citation

George Giakkoupis, Anne-Marie Kermarrec, Philipp Woelfel. Gossip protocols for renaming and sorting. DISC - 27th International Symposium on Distributed Computing, Oct 2013, Jerusalem, Israel. 2013. 〈hal-00875162〉

Partager

Métriques

Consultations de la notice

415

Téléchargements de fichiers

207