Back to Search
Start Over
On convergence and threshold properties of discrete Lotka-Volterra population protocols.
- Source :
-
Journal of Computer & System Sciences . Dec2022, Vol. 130, p1-25. 25p. - Publication Year :
- 2022
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYNOMIAL time algorithms
*LOTKA-Volterra equations
*DISTRIBUTED algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 130
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 158609309
- Full Text :
- https://doi.org/10.1016/j.jcss.2022.06.002