James Aspnes. Clocked population protocols. ACM Symposium on Principles of Distributed Computing (PODC 2017), July 2017, pp. 431–440.

Population protocols are required to converge to the correct answer, and are subject to a fairness condition that guarantees eventual progress, but generally have no internal mechanism for detecting when this progress has occurred. 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. To simplify the model, we represent “long enough” as an infinite time interval, and treat a clocked population protocol as operating over transfinite time. This gives a clean theoretical model that we show how to translate back into finite real-world executions where the clock ticks whenever the underlying protocol is looping or stuck.

Over finite time intervals, the protocol behaves as in the standard model. At nonzero limit ordinals ω, ω⋅2, etc., corresponding to clock ticks, the protocol switches to a limit of previous configurations supplemented by an signal registering in an extra component in some of the agents' states. Using transfinite times means that we can represent fairness over sequences of transitions that may include clock ticks with the same definition as over smaller intervals. Using arbitrary ordinals allows using times like ω² or ω³ to represent convergence that depends on detecting convergence repeatedly at lower levels.

We show that a clocked population protocol running in ω^{k} time
is equivalent in power
to a nondeterministic Turing machine with space complexity
logarithmic in the size of the population.
A consequence of this equivalence is that any symmetric predicate computed
by such a protocol can be computed
in less than $ω² time, which requires only finitely many clock ticks.

- Full version:
**PDF**. - PODC 2017 proceedings version: PDF.
- Slides from James Aspnes's talk at PODC 2017: PDF.

@inproceedings{Aspnes17, author = {James Aspnes}, editor = {Elad Michael Schiller and Alexander A. Schwarzmann}, title = {Clocked Population Protocols}, booktitle = {Proceedings of the {ACM} Symposium on Principles of Distributed Computing, {PODC} 2017, Washington, DC, USA, July 25-27, 2017}, pages = {431--440}, publisher = {{ACM}}, year = {2017}, url = {http://doi.acm.org/10.1145/3087801.3087836}, doi = {10.1145/3087801.3087836}, timestamp = {Fri, 21 Jul 2017 13:32:16 +0200}, biburl = {http://dblp.dagstuhl.de/rec/bib/conf/podc/Aspnes17}, bibsource = {dblp computer science bibliography, http://dblp.org} }

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page