×

Fixation for distributed clustering processes. (English) Zbl 1202.60156

The authors consider the following process on the vertices of \(\mathbb Z^d\), where \(d \geq 1\). Assume that initially every vertex \(x\) has a load \(C_0(x)\). At each round each node transfers its load to the neighbouring node with the maximal load. The authors show that for any initial translation-invariant distribution of the load, at each vertex the process almost surely stops after finitely many steps. Their proof also applies to other lattices such as Cayley graphs and infinite regular trees, with a slight modification.

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60D05 Geometric probability and stochastic geometry
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] van den Berg, On a distributed clustering process of Coffman, Courtois, Gilbert and Piret, J. Appl. Probab. 35 pp 919– (1998) · Zbl 0931.60084
[2] van den Berg, J.; Hilário, M. R.; Holroyd, A. In preparation.
[3] van den Berg, Stability properties of a flow process in graphs, Random Structures Algorithms 2 pp 335– (1991) · Zbl 0741.05072
[4] Coffman, A distributed clustering process, J. Appl. Probab. 28 pp 737– (1991) · Zbl 0741.60114
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.