Probabilistic non-asymptotic analysis of distributed algorithms

Abstract : We present a new probabilistic analysis of distributed algorithms. Our approach relies on the theory of quasi-stationary distributions (QSD) recently developped by the first and third authors [4, 5, 6]. We give properties on the deadlock time and the distribution of the model before deadlock, both for discrete and diffusion models. Our results are non-asymptotic since they apply to any finite values of the involved parameters (time, numbers of resources, number of processors, etc.) and reflect the real behavior of these algorithms, with potential applications to deadlock prevention, which are very important for real world applications in computer science.
Liste complète des métadonnées

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-01710663
Contributor : Nicolas Champagnat <>
Submitted on : Friday, February 16, 2018 - 11:20:27 AM
Last modification on : Friday, April 19, 2019 - 4:54:58 PM
Document(s) archivé(s) le : Saturday, May 5, 2018 - 3:53:11 PM

File

2018_02_CSV.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-01710663, version 1

Citation

Nicolas Champagnat, René Schott, Denis Villemonais. Probabilistic non-asymptotic analysis of distributed algorithms. 2018. ⟨hal-01710663⟩

Share

Metrics

Record views

354

Files downloads

35