The Dynamics of Probabilistic Population Protocols

Simple item page
dc.creatorChatzigiannakis, Ioannis
dc.creatorSpirakis, Paul G.
dc.date2008-07-01
dc.date.accessioned2026-07-07T09:47:38Z
dc.date.available2026-07-07T09:47:38Z
dc.descriptionWe study here the dynamics (and stability) of Probabilistic Population Protocols, via the differential equations approach. We provide a quite general model and we show that it includes the model of Angluin et. al. in the case of very large populations. For the general model we give a sufficient condition for stability that can be checked in polynomial time. We also study two interesting subcases: (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.
dc.descriptionTo appear as a Brief Announced in Proc. of 22nd International Symposium on Distributed Computing (DISC 2008), September 22-24, 2008, Arcachon, France
dc.identifierhttps://arxiv.org/abs/0807.0140
dc.identifierhttp://arxiv.org/abs/0807.0140
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/163952
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectComputer Science and Game Theory
dc.subjectC.2.4; C.2.1; F.1.1; F.1.2
dc.titleThe Dynamics of Probabilistic Population Protocols
dc.typetext

Files

Collections

arXiv