Efficient self-stabilizing construction of disjoint MDSs in distance-2 model - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2021

Efficient self-stabilizing construction of disjoint MDSs in distance-2 model

Résumé

We study the deterministic silent self-stabilizing construction of two disjoint minimal dominating sets (MDSs) in anonymous networks. We focus on algorithms where nodes share only their status (i.e. the name of their MDS to which they belong, if they belong to a MDS). We prove that such an algorithm cannot be designed in distance-1 model under a central daemon; therefore, we study this problem in the distance-2 model under a central daemon. We present an algorithm building two disjoint minimal dominating sets such that one of them is also a maximal independent set (MIS). Any execution of this algorithm converges in 5n moves. Our approach to compute this value is novel: the number of moves is not computed per node. We propose a second algorithm faster than the first one at the expense of the independence property of one of the constructed sets. A node executes at most 2 moves. If the network is not anonymous, the presented algorithms can be translated into a silent self-stabilizing algorithms converging in O($n$•$m$) moves in the distance-1 model under the distributed daemon where m is the number of edges and n the number of nodes. This improves the complexity of O($n$.$m$) moves of proposed algorithms with the same assumptions.
Fichier principal
Vignette du fichier
disjointMDS.pdf (308.25 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03138979 , version 1 (11-02-2021)

Identifiants

  • HAL Id : hal-03138979 , version 1

Citer

Colette Johnen, Mohammed Haddad. Efficient self-stabilizing construction of disjoint MDSs in distance-2 model. [Research Report] Inria Paris, Sorbonne Université; LaBRI, CNRS UMR 5800; LIRIS UMR CNRS 5205. 2021. ⟨hal-03138979⟩
136 Consultations
76 Téléchargements

Partager

Gmail Facebook X LinkedIn More