Clocked population protocols

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

Abstract

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.

BibTeX

Download
@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