Escape of resources in a distributed clustering process

DOI10.1214/ECP.V15-1567MaRDI QIDQ638222zbMATH OpenOpenAlexFDO

Authors Marcelo Richard Hilário, A. E. Holroyd, Jacob van den Berg

Publication date 9 September 2011

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.2426, http://www.emis.de/journals/EJP-ECP/_ejpecp/ECP/viewarticled14a.html

zbMATH Keywords

clustering processrandom spanning tree

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Distributed systems (68M14)

Abstract: In a distributed clustering algorithm introduced by Coffman, Courtois, Gilbert and Piret cite{coffman91}, each vertex of $mathbb{Z}^d$ receives an initial amount of a resource, and, at each iteration, transfers all of its resource to the neighboring vertex which currently holds the maximum amount of resource. In cite{hlrnss} it was shown that, if the distribution of the initial quantities of resource is invariant under lattice translations, then the flow of resource at each vertex eventually stops almost surely, thus solving a problem posed in cite{berg91}. In this article we prove the existence of translation-invariant initial distributions for which resources nevertheless escape to infinity, in the sense that the the final amount of resource at a given vertex is strictly smaller in expectation than the initial amount. This answers a question posed in cite{hlrnss}.

Recommendations

• On a distributed clustering process of Coffman, Courtois, Gilbert and Piret
• Distributed algorithms with dynamical random transitions
• Fixation for distributed clustering processes
• A distributed clustering process
• Asymmetrical resource networks. I. Stabilization processes for low resources

Cited in

(2)

• A distributed clustering process
• Fixation for distributed clustering processes

This page was built for publication: Escape of resources in a distributed clustering process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638222)