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

Leave a Reply

Your email address will not be published.

162,982 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>