New Clocks, Optimal Line Formation and Efficient Replication Population Protocols (Making Population Protocols Alive)
share
We consider the model of population protocols permitting presence of dynamically changing edges connecting agents. Our main contribution is a new constant space phase clock allowing to count parallel time O(nlog n) whp in the adopted model. This clock admits confirmation of slow leader election and in turn construction of a line (and a ring) comprising every agent in the optimal parallel time Θ(nlog n) and constant space. This improves on the currently best known upper bound O(n^2). We also discuss a variant of the new clock in which utilisation of edges is replaced by interaction of agents with a unique leader. This variant provides a universal (for models with and without edges) synchronisation mechanism and is adopted in some of our efficient line replication protocols.
READ FULL TEXT