Abstract | We extend here the Population Protocol model of Angluin et al. [2004] in order to model more powerful networks of very small resource-limited artefacts (agents) that are possibly mobile. Communication can happen only between pairs of artefacts. A communication graph (or digraph) denotes the permissible pairwise interactions. The main feature of our extended model is to allow edges of the communication graph, G, to have states that belong to a constant size set. We also allow edges to have readable only costs, whose values also belong to a constant size set. We then allow the protocol rules for pairwise interactions to modify the corresponding edge state. Thus, our protocol specifications are still independent of the population size and do not use agent ids, i.e. they preserve scalability, uniformity and anonymity. Our Mediated Population Protocols (MPP) can stably compute graph properties of the communication graph. We show this for the properties of maximal matchings (in undirected communication graphs), also for finding the transitive closure of directed graphs and for finding all edges of small cost. We demonstrate that our mediated protocols are stronger than the classical population protocols, by presenting a mediated protocol that stably computes the product of two positive integers, when G is the complete graph. This is not a semilinear predicate. To show this fact, we state and prove a general Theorem about the Composition of two stably computing mediated population protocols. We also show that all predicates stably computable in our model are (non-uniformly) in the class NSPACE(m), where m is the number of edges of the communication graph. We also define Randomized MPP and show that, any Peano predicate accepted by a MPP, can be verified in deterministic Polynomial Time. |