Optimal Time Self-Stabilization in Uniform Dynamic Systems

Publisher Website
Google Scholar
Abstract
In this paper we present a randomized uniform self-stabilizing protocol that provides each (anonymous) processor of a uniform system with a distinct identifier. The protocol uses a predefined fixed amount of memory and stabilizes within expected Θ(d) time, where d is the actual diameter of the network. The naming protocol can be combined with self-stabilizing protocols that assume distinct identifiers for the processors. Thus, we achieve with optimal time and predefined amount of memory uniform self-stabilizing protocols for many tasks including: Spanning tree construction, leader election and reset.

This publication has 0 references indexed in Scilit: