Title :
An implementable dynamic automatic self-stabilizing protocol
Author :
Flauzac, O. ; Villain, V.
Author_Institution :
CNRS, Compiegne, France
Abstract :
The notion of self-stabilization was first introduced by Dijkstra: it is the property for a system to eventually recover by itself a legitimate state after any perturbation modifying the memory state. This paper proposes a dynamic automatic self-stabilizing protocol. This algorithm runs in the fully asynchronous message-passing model in which messages can also be corrupted. The principle of the algorithm is to compute regularly a global state and if necessary to generate a global reset. When the system is stabilized, the message complexity is O(max(δ*m, n2)) where δ is the degree of the communication graph, m the number of links and n the number of processors. This complexity allows a possible implementation
Keywords :
communication complexity; fault tolerant computing; message passing; protocols; asynchronous message-passing; automatic self-stabilization; distributed systems; fault-tolerance; fully asynchronous message passing; message complexity; self-stabilization; self-stabilizing protocol; superimposition; Channel capacity; Communication channels; Distributed algorithms; Fault tolerant systems; Message passing; Protocols; System testing;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 1997. (I-SPAN '97) Proceedings., Third International Symposium on
Conference_Location :
Taipei
Print_ISBN :
0-8186-8259-6
DOI :
10.1109/ISPAN.1997.645076