Chatzigiannakis, Ioannis and Spirakis, Paul ORCID: 0000-0001-5396-3749
(2017)
The Dynamics and Stability of Probabilistic Population Processes.
In: 19th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS 2017), 2017-11-5 - 2017-11-8, Boston USA.
Text
SSS-stability.pdf - Author Accepted Manuscript Download (219kB) |
Abstract
We study here the dynamics and stability of Probabilistic Population Processes, via the differential equations approach. We provide a quite general model following the work of Kurtz [15] for approximating discrete processes with continuous differential equations. We show that it includes the model of Angluin et al. [1], in the case of very large populations. We require that the long-term behavior of the family of increasingly large discrete processes is a good approximation to the long-term behavior of the continuous process, i.e., we exclude population protocols that are extremely unstable such as parity-dependent decision processes. For the general model, we give a sufficient condition for stability that can be checked in polynomial time. We also study two interesting sub cases: (a) Protocols whose specifications (in our terms) are configuration independent. We show that they are always stable and that their eventual subpopulation percentages are actually a Markov Chain stationary distribution. (b) Protocols that have dynamics resembling virus spread. We show that their dynamics are actually similar to the well-known Replicator Dynamics of Evolutionary Games. We also provide a sufficient condition for stability in this case.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Depositing User: | Symplectic Admin |
Date Deposited: | 22 Aug 2017 09:00 |
Last Modified: | 18 Mar 2024 01:35 |
DOI: | 10.1007/978-3-319-69084-1_3 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3009077 |