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.37
URN: urn:nbn:de:0030-drops-113442
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11344/
Go to the corresponding LIPIcs Volume Portal

Blin, Lélia ; Feuilloley, Laurent ; Le Bouder, Gabriel

Brief Announcement: Memory Lower Bounds for Self-Stabilization

pdf-format:
LIPIcs-DISC-2019-37.pdf (0.3 MB)

Abstract

In the context of self-stabilization, a silent algorithm guarantees that the communication registers (a.k.a register) of every node do not change once the algorithm has stabilized. At the end of the 90's, Dolev et al. [Acta Inf. '99] showed that, for finding the centers of a graph, for electing a leader, or for constructing a spanning tree, every silent deterministic algorithm must use a memory of Omega(log n) bits per register in n-node networks. Similarly, Korman et al. [Dist. Comp. '07] proved, using the notion of proof-labeling-scheme, that, for constructing a minimum-weight spanning tree (MST), every silent algorithm must use a memory of Omega(log^2n) bits per register. It follows that requiring the algorithm to be silent has a cost in terms of memory space, while, in the context of self-stabilization, where every node constantly checks the states of its neighbors, the silence property can be of limited practical interest. In fact, it is known that relaxing this requirement results in algorithms with smaller space-complexity.
In this paper, we are aiming at measuring how much gain in terms of memory can be expected by using arbitrary deterministic self-stabilizing algorithms, not necessarily silent. To our knowledge, the only known lower bound on the memory requirement for deterministic general algorithms, also established at the end of the 90's, is due to Beauquier et al. [PODC '99] who proved that registers of constant size are not sufficient for leader election algorithms. We improve this result by establishing the lower bound Omega(log log n) bits per register for deterministic self-stabilizing algorithms solving (Delta+1)-coloring, leader election or constructing a spanning tree in networks of maximum degree Delta.

BibTeX - Entry

@InProceedings{blin_et_al:LIPIcs:2019:11344,
  author =	{L{\'e}lia Blin and Laurent Feuilloley and Gabriel Le Bouder},
  title =	{{Brief Announcement: Memory Lower Bounds for Self-Stabilization}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{37:1--37:3},
  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/11344},
  URN =		{urn:nbn:de:0030-drops-113442},
  doi =		{10.4230/LIPIcs.DISC.2019.37},
  annote =	{Keywords: Space lower bound, memory tight bound, deterministic self-stabilization, leader election, anonymous, identifiers, state model, ring}
}

Keywords: Space lower bound, memory tight bound, deterministic self-stabilization, leader election, anonymous, identifiers, state model, ring
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