Clocked population protocols

摘要

We define an extension to the standard population protocol that provides each agent with a clock signal that indicates when the agent has waited long enough for the protocol to have converged. We represent “long enough” as an infinite time interval, and treat the protocol as operating over transfinite time. Over finite time intervals, the protocol behaves as in the standard model. At nonzero limit ordinals, corresponding to clock ticks, the protocol switches to a limit of previous configurations supplemented by a clock signal appearing as an extra component in some of the agents' states. Fairness generalizes to transfinite executions straightforwardly. We show that a clocked population protocol running in less than ωk time for any fixed k≥2 is equivalent in power to a nondeterministic Turing machine with space complexity logarithmic in the population size, and can be simulated using only finitely many clock ticks.