James Aspnes. Clocked population protocols. Journal of Computing and System Sciences 121:34–48, 2021. An earlier version appeared in ACM Symposium on Principles of Distributed Computing (PODC 2017), July 2017, pp. 431–440.
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 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.
@article{Aspnes2021,
author = {James Aspnes},
title = {Clocked population protocols},
journal = {J. Comput. Syst. Sci.},
volume = {121},
pages = {34--48},
year = {2021},
url = {https://doi.org/10.1016/j.jcss.2021.05.001},
doi = {10.1016/j.jcss.2021.05.001},
timestamp = {Wed, 09 Jun 2021 08:38:55 +0200},
biburl = {https://dblp.org/rec/journals/jcss/Aspnes21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}