Immediate Observation in Mediated Population Protocols

Tobias Prehn
(Technische Universität Berlin)
Myron Rotter
(Technische Universität Berlin)

In this paper we analyze the computational power of variants of population protocols (PP), a formalism for distributed systems with anonymous agents having very limited capabilities. The capabilities of agents are enhanced in mediated population protocols (MPP) by recording the states in the edges of the interaction graph. Restricting the interactions to the communication model of immediate observation (IO) reduces the computational power of the resulting formalism. We show that this enhancement and restriction, when combined, yield a model (IOMPP) at least as powerful as the basic PP. The proof requires a novel notion of configurations in the MPP model allowing differentiation of agents and uses techniques similar to methods of analyzing encoding criteria, namely operational correspondence. The constructional part of the proof is generic in a way that all protocols can be translated into the new model without losing the desirable properties they might have besides a stable output. Furthermore, we illustrate how this approach could be utilized to prove our conjecture of IOMPP model being even as expressive as the MPP model. If our conjecture holds, this would result in a sharp characterization of the computational power and reveal the nonnecessity of two-way communication in the context of mediated population protocols.

In Jorge A. Pérez and Jurriaan Rot: Proceedings Combined 26th International Workshop on Expressiveness in Concurrency and 16th Workshop on Structural Operational Semantics (EXPRESS/SOS 2019), Amsterdam, The Netherlands, 26th August 2019, Electronic Proceedings in Theoretical Computer Science 300, pp. 102–113.
Published: 22nd August 2019.

ArXived at: https://dx.doi.org/10.4204/EPTCS.300.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org