Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : George Giakkoupis Connect in order to contact the contributor
Submitted on : Monday, October 21, 2013 - 12:20:24 PM
Last modification on : Thursday, January 20, 2022 - 4:20:36 PM
Long-term archiving on: : Wednesday, January 22, 2014 - 4:26:18 AM


Files produced by the author(s)


  • HAL Id : hal-00875162, version 1


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



Record views


Files downloads