Gossip Protocols for Renaming and Sorting

George Giakkoupis, Anne-Marie Kermarrec, and Philipp Woelfel


Abstract: We devise efficien 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 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. A variant of this protocol solves the tight renaming problem, where each node obtains a unique ID in {1,…,n}, in O(log^2 n) rounds. Next we study the following 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 [20] 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.

Guest: George Giakkoupis

Host: Stefan Schmid

Optimal-Time Adaptive Strong Renaming with Applications to Counting

Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert and Morteza Zadimoghaddam

Abstract: We give two new randomized algorithms for strong renaming, both of which work against an adaptive adversary in asynchronous shared memory. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity O(log^3 n). The second transforms any sorting network into a strong adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a strong adaptive renaming algorithm with step complexity O(log k), where k is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such strong renaming protocol can be used to build a
monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor).

Guest: Dan Alistarh
Host: Yvonne-Anne Pignolet