Abstract | We work on an extension of the Population Protocol model
of Angluin et al. [1] that allows edges of the communication graph, G, to
have states that belong to a constant size set. In this extension, the so
called Mediated Population Protocol model (MPP) [2,3], both uniformity
and anonymity are preserved.We here study a simplified version of MPP,
the Graph Decision Mediated Population Protocol model (GDM), in
order to capture MPP's ability to decide graph languages. We also prove
some first impossibility results both for weakly connected and possibly
disconnected communication graphs. |