License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.9
URN: urn:nbn:de:0030-drops-113161
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11316/
Go to the corresponding LIPIcs Volume Portal

Burman, Janna ; Beauquier, Joffroy ; Sohier, Devan

Space-Optimal Naming in Population Protocols

pdf-format:
LIPIcs-DISC-2019-9.pdf (0.5 MB)

Abstract

The distributed naming problem, assigning unique names to the nodes in a distributed system, is a fundamental task. This problem is nontrivial, especially when the amount of memory available for the task is low, and when requirements for fault-tolerance are added.
The considered distributed communication model is population protocols. In this model, a priori anonymous and indistinguishable mobile nodes (called agents), communicate in pairs and in an asynchronous manner (according to a fairness condition). Fault-tolerance is addressed through self-stabilization, in terms of arbitrary initialization of agents.
This work comprises a comprehensive study of the necessary and sufficient state space conditions for naming. The problem is studied under various combinations of model assumptions: weak or global fairness, arbitrary or uniform initialization of agents, existence or absence of a distinguishable agent (arbitrarily initialized or not), possibility of breaking symmetry in pair-wise interactions (symmetric or asymmetric transitions). For each possible combination of these assumptions, either an impossibility is proven or the necessary exact number of states (per mobile agent) is determined and an appropriate space-optimal naming protocol is presented.

BibTeX - Entry

@InProceedings{burman_et_al:LIPIcs:2019:11316,
  author =	{Janna Burman and Joffroy Beauquier and Devan Sohier},
  title =	{{Space-Optimal Naming in Population Protocols}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11316},
  URN =		{urn:nbn:de:0030-drops-113161},
  doi =		{10.4230/LIPIcs.DISC.2019.9},
  annote =	{Keywords: networks of passively mobile agents, population protocols, deterministic naming, self-stabilization, exact space complexity, tight lower bounds, glob}
}

Keywords: networks of passively mobile agents, population protocols, deterministic naming, self-stabilization, exact space complexity, tight lower bounds, glob
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI