Skip to Main content Skip to Navigation
Journal articles

Stochastic Analysis of Average Based Distributed Algorithms

Yves Mocquard 1 Bruno Sericola 2 Frédérique Robin 3 Emmanuelle Anceaume 3 
1 MINGUS - Multi-scale numerical geometric schemes
IRMAR - Institut de Recherche Mathématique de Rennes, ENS Rennes - École normale supérieure - Rennes, Inria Rennes – Bretagne Atlantique
2 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
Inria Rennes – Bretagne Atlantique , IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
3 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : We analyse average-based distributed algorithms relying on simple and pairwise random interactions among a large and unknown number of anonymous agents. This allows the characterization of global properties emerging from these local interactions. Agents start with an initial integer value, and at each interaction keep the average integer part of both values as their new value. The convergence occurs when, with high probability, all the agents possess the same value which means that they all know a property of the global system. Using a well chosen stochastic coupling, we improve upon existing results by providing explicit and tight bounds of the convergence time. We apply these general results to both the proportion problem and the system size problem.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal-cnrs.archives-ouvertes.fr/hal-02473856
Contributor : Emmanuelle Anceaume Connect in order to contact the contributor
Submitted on : Tuesday, February 11, 2020 - 9:00:29 AM
Last modification on : Friday, August 5, 2022 - 2:54:52 PM
Long-term archiving on: : Tuesday, May 12, 2020 - 12:40:41 PM

File

main_JAP.pdf
Files produced by the author(s)

Identifiers

Citation

Yves Mocquard, Bruno Sericola, Frédérique Robin, Emmanuelle Anceaume. Stochastic Analysis of Average Based Distributed Algorithms. Journal of Applied Probability, Cambridge University press, 2021, 58 (2), pp.394 - 410. ⟨10.1017/jpr.2020.97⟩. ⟨hal-02473856⟩

Share

Metrics

Record views

155

Files downloads

225