Expressive power of broadcast consensus protocols

Michael Blondin, Javier Esparza, Stefan Jaax

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

Population protocols are a formal model of computation by identical, anonymous mobile agents interacting in pairs. Their computational power is rather limited: Angluin et al. have shown that they can only compute the predicates over ℕk expressible in Presburger arithmetic. For this reason, several extensions of the model have been proposed, including the addition of devices called cover-time services, absence detectors, and clocks. All these extensions increase the expressive power to the class of predicates over ℕk lying in the complexity class NL when the input is given in unary. However, these devices are difficult to implement, since they require that an agent atomically receives messages from all other agents in a population of unknown size; moreover, the agent must know that they have all been received. Inspired by the work of the verification community on Emerson and Namjoshi’s broadcast protocols, we show that NL-power is also achieved by extending population protocols with reliable broadcasts, a simpler, standard communication primitive.

Original languageEnglish
Title of host publication30th International Conference on Concurrency Theory, CONCUR 2019
EditorsWan Fokkink, Rob van Glabbeek
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771214
DOIs
StatePublished - Aug 2019
Event30th International Conference on Concurrency Theory, CONCUR 2019 - Amsterdam, Netherlands
Duration: 27 Aug 201930 Aug 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume140
ISSN (Print)1868-8969

Conference

Conference30th International Conference on Concurrency Theory, CONCUR 2019
Country/TerritoryNetherlands
CityAmsterdam
Period27/08/1930/08/19

Keywords

  • Complexity theory
  • Counter machines
  • Distributed computing
  • Population protocols

Fingerprint

Dive into the research topics of 'Expressive power of broadcast consensus protocols'. Together they form a unique fingerprint.

Cite this