From self- to self-stabilizing with service guarantee 1-hop weight-based clustering

We propose a transformer building a silent self-stabilizing with service guarantee 1-hop clustering protocol TP of an input silent self-stabilizing 1-hop clustering protocol P. From an arbitrary con figuration, TP reaches a safe con figuration in at most 3 rounds, where the following useful minimal service is provided: "each node belongs to a 1-hop cluster having an effectual leader". During stabilization of TP protocol, the minimal service is preserved, so the clustering structure is available throughout the entire network. The minimal service is also maintained despite the occurrences of some external disruptions, called highly tolerated disruptions, denoted HTD. TP protocol reaches a terminal (also legitimate) con figuration in at most 4*SP rounds where SP is the stabilization time of P protocol. Moreover, TP requires only 2 bits per node more than P protocol.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00716281
Author Johnen, Colette, Mekhaldi, Fouzi
Maintainer CCSD
Last Updated November 5, 2026, 05:41 (UTC)
Created November 5, 2026, 05:41 (UTC)
Identifier hal-00716281
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire Bordelais de Recherche en Informatique (LaBRI) ; Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
creator Johnen, Colette
date 2012-06-06T00:00:00
harvest_object_id ef7812ba-24d6-407d-9a76-b5bf56163a62
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-05-26T00:00:00
set_spec type:REPORT