# Gossip protocols for renaming and sorting

1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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.
Document type :
Conference papers

Cited literature [30 references]

https://hal.inria.fr/hal-00875162
Contributor : George Giakkoupis <>
Submitted on : Monday, October 21, 2013 - 12:20:24 PM
Last modification on : Tuesday, June 15, 2021 - 4:14:47 PM
Long-term archiving on: : Wednesday, January 22, 2014 - 4:26:18 AM

### File

disc13_sorting.pdf
Files produced by the author(s)

### Identifiers

• 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. ⟨hal-00875162⟩

Record views