  The following distributed coalescence protocol was introduced by Dahlia
Malkhi in 2006 motivated by applications in social networking. Initially there
are n agents wishing to coalesce into one cluster via a decentralized
stochastic process, where each round is as follows: every cluster flips a fair
coin to dictate whether it is to issue or accept requests in this round.
Issuing a request amounts to contacting a cluster randomly chosen
proportionally to its size. A cluster accepting requests is to select an
incoming one uniformly (if there are such) and merge with that cluster.
Empirical results by Fernandess and Malkhi suggested the protocol concludes in
O(log n) rounds with high probability, whereas numerical estimates by Oded
Schramm, based on an ingenious analytic approximation, suggested that the
coalescence time should be super-logarithmic. Our contribution is a rigorous
study of the stochastic coalescence process with two consequences. First, we
confirm that the above process indeed requires super-logarithmic time w.h.p.,
where the inefficient rounds are due to oversized clusters that occasionally
develop. Second, we remedy this by showing that a simple modification produces
an essentially optimal distributed protocol; if clusters favor their smallest
incoming merge request then the process does terminate in O(log n) rounds
w.h.p., and simulations show that the new protocol readily outperforms the
original one. Our upper bound hinges on a potential function involving the
logarithm of the number of clusters and the cluster-susceptibility, carefully
chosen to form a supermartingale. The analysis of the lower bound builds upon
the novel approach of Schramm which may find additional applications: rather
than seeking a single parameter that controls the system behavior, instead one
approximates the system by the Laplace transform of the entire cluster-size
distribution.
