Fixation for Distributed Clustering Processes.

Abstract: We study a distributed clustering algorithm introduced by
Coffman, Courtois, Gilbert and Piret. At time $t=0$ a random amount of a
resource is placed on each vertex of the $d$-dimensional integer lattice.
Then, at each step, each vertex transfers all its resource to the vertex
which currently maximizes the amount of resources within the unit ball
around it. We prove that, if the initial resource quantities are sampled
from any translation-invariant probability distribution then the flow at
each vertex stops after finitely many steps almost surely. This answers a
(generalized version) of a question posed by Van den Berg and Meester in
1991. (Joint work with: O. Luidor, C. M. Newman, L. T. Rolla, S. Sheffield
and V. Sidoravicius.)