Misc,
Constructive expressive power of population protocols
(2020)http://arxiv.org/abs/2002.07303.
Abstract
Population protocols are a model of distributed computation intended for the
study of networks of independent computing agents with dynamic communication
structure. Each agent has a finite number of states, and communication
opportunities occur nondeterministically, allowing the agents involved to
change their states based on each other's states. Population protocols are
often studied in terms of reaching a consensus on whether the input
configuration satisfied some predicate.
In the present paper we propose an alternative point of view. Instead of
studying the properties of inputs that a protocol can recognise, we study the
properties of outputs that a protocol eventually ensures. We define
constructive expressive power. We show that for general population protocols
and immediate observation population protocols the constructive expressive
power coincides with the normal expressive power.
Immediate observation protocols also preserve their relatively low
verification complexity in the constructive expressive power setting.
