Distributed population protocols: naturally!

Abstract

Classical population protocols manage a fix size population of agents that are created by the input population: one agent exactly per unit of the input. As a consequence, complex protocols that have to perform several independent tasks find here a clear bottleneck that drastically reduces the parallelism in the execution of those tasks. To solve this problem, I propose to manage distributed population protocols, that simply generalize the classical ones by generating a (fix, finite) set of agents per each unit of the input. A surprising fact is that these protocols are not really new, if instead of considering only the classical protocols with an input alphabet we consider the alternative simpler one that states as input mechanism a given subset of the set of states. Distributed population protocols are not only interesting because they allow more parallel and faster executions, but specially because the distribution of both code and data will allow much simpler protocols, inspired by the distribution of both places and transitions in Petri nets.