Balls-into-Leaves: Sub-Logarithmic Renaming in Synchronous Message-Passing Systems

We consider the following natural problem: n failure-prone servers, communicating synchronously through message-passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of Omega (log n) communication rounds is known. Second, model the problem as a randomized load-balancing problem, which have elegant sub-logarithmic solutions. However, careful examination reveals that such solutions do not really apply to our scenario, because they are not fault tolerant or do not ensure one-to-one allocation. It is thus natural to ask if sub-logarithmic solutions exist for this apparently simple but intriguing problem.
In this paper, we combine the two approaches to provide a new randomized solution for tight renaming, which terminates in O(log log n) communication rounds with high probability, against a strong adaptive adversary. Our solution, called Balls-into-Leaves, combines the deterministic approach with a new randomized scheme to obtain perfectly balanced allocations. The algorithm arranges the items as leaves of a tree, and participants repeatedly perform random choices among the leaves. The algorithm exchanges information in each round to split the participants into progressively smaller groups whose random choices do not conflict. An extension of the algorithm terminates early in O(log log f) rounds w.h.p., where f is the actual number of failures. These results imply an exponential separation between deterministic and randomized algorithms for the tight renaming problem in message-passing systems.