Immediate Observation in Mediated Population Protocols

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.

• Publication year

  2019

• Venue

  Combined International Workshop Expressiveness Concurrency and Workshop Structural Operational Semantics

• Publication date

  2019-08-22

• Fields of study

  Medicine, Computer Science

• Identifiers
  DOI 10.4204/EPTCS.300.7arXiv 1908.08637
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Mediated Population Protocols: Leader Election and Applications

  2017cited by this paper
• Verification of population protocols

  2016cited by this paper
• Fast and Exact Majority in Population Protocols

  2015cited by this paper
• Mediated Population Protocols

  2009influential reference
• Towards a unified approach to encodability and separation results for process calculi

  2008influential reference
• An Introduction to Population Protocols

  2007cited by this paper
• The computational power of population protocols

  2006cited by this paper
• When Birds Die: Making Population Protocols Fault-Tolerant

  2006cited by this paper
• Self-stabilizing population protocols

  2005cited by this paper
• Computation in networks of passively mobile finite-state sensors

  2004cited by this paper

• No citing papers are available for this paper.