Spirakis, Paul 
ORCID: 0000-0001-5396-3749, Czyzowicz, Jurek, Gasieniec, Lezsek ORCID: 0000-0003-1809-9814, Kosowski, Adrian, Kranakis, Evangelos and Uznanski, Przemyslaw
(2022)
On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols.
Journal of Computer and System Sciences, 130.
pp. 1-25.
|
Text
population-final.pdf - Author Accepted Manuscript Download (853kB) | Preview |
Abstract
We study population protocols whose dynamics are modeled by the discrete Lotka-Volterra equations. Such protocols capture the dynamics of some opinion spreading models and generalize the Rock-Paper-Scissors discrete dynamics. Pairwise interactions among agents are scheduled uniformly at random. We consider convergence time and show that any such protocol on an n-agent population converges to an absorbing state in time polynomial in n, w.h.p., when any pair of agents is allowed to interact. When the interaction graph is a star, even the Rock-Paper-Scissors protocol requires exponential time to converge. We study threshold effects with three and more species under interactions between any pair of agents. We prove that the Rock-Paper-Scissors protocol reaches each of its three possible absorbing states with almost equal probability, starting from any configuration satisfying some sub-linear lower bound on the initial size of each species. Thus Rock-Paper-Scissors is a realization of “coin-flip consensus” in a distributed system.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Agents, Discretedynamics, Lotka-Voltera, Paper-rock-scissors, Populationprotocols |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 16 Jun 2022 13:40 |
| Last Modified: | 06 Oct 2023 01:57 |
| DOI: | 10.1016/j.jcss.2022.06.002 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3156594 |
Dimensions
Dimensions
