Token-Based Self-Stabilizing Uniform Algorithms
- Others:
- Laboratoire de Recherche en Informatique (LRI) ; CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)
- Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Citation
Description
This work focuses on self-stabilizing algorithms for mutual exclusion and leader election—two fundamental tasks for distributed systems. Self-stabilizing systems are able to recover by themselves, regaining their consistency from any initial or intermediary faulty configuration. The proposed algorithms are designed for any directed, anonymous network and stabilize under any distributed scheduler. The keystones of the algorithms are the token management and routing policies. In order to break the network symmetry, randomization is used. The space complexity is O((D^++D^−)(log(snd(n))+2)) where n is the network size, snd(n) is the smallest integer that does not divide n and D+ and D− are the maximal out and in degree, respectively. It should be noted that snd(n) is constant on the average and equals 2 on odd-size networks.
Abstract
International audience
Additional details
- URL
- https://hal.archives-ouvertes.fr/hal-03277271
- URN
- urn:oai:HAL:hal-03277271v1
- Origin repository
- UNICA