Population Protocols Made Easy
share
We put forward a simple high-level framework for describing a population protocol, which includes the capacity for sequential execution of instructions and a (limited) capacity for loops and branching instructions. The process of translation of the protocol into its standard form, i.e., into a collection of asynchronously executed state-transition rules, is performed by exploiting nested synchronization primitives based on tunable phase-clocks, in a way transparent to the protocol designer. The framework is powerful enough to allow us to easily formulate protocols for numerous problems, including leader election and majority. The framework also comes with efficiency guarantees on any protocol which can be expressed in it. We provide a set of primitives which guarantee O(n^ε) time keeping O(1) states, for any choice of ε > 0, or polylogarithmic time using O( n) states. These tradeoffs improve the state-of-the-art for both leader election and majority.
READ FULL TEXT