Abstract
In the context of selfstabilization, 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 nnode networks. Similarly, Korman et al. [Dist. Comp. '07] proved, using the notion of prooflabelingscheme, that, for constructing a minimumweight 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 selfstabilization, 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 spacecomplexity.
In this paper, we are aiming at measuring how much gain in terms of memory can be expected by using arbitrary deterministic selfstabilizing 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 selfstabilizing 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 SelfStabilization}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {37:137:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771269},
ISSN = {18688969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11344},
URN = {urn:nbn:de:0030drops113442},
doi = {10.4230/LIPIcs.DISC.2019.37},
annote = {Keywords: Space lower bound, memory tight bound, deterministic selfstabilization, leader election, anonymous, identifiers, state model, ring}
}
Keywords: 

Space lower bound, memory tight bound, deterministic selfstabilization, 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 