1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97)
An Implementable Dynamic Automatic Self-Stabilizing Protocol
Taipei, Taiwan
December 18-December 20
ISBN: 0-8186-8259-0
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(D *m,n^2)) where D is the degree of the communication graph, m the number of links and n the number of processes. This complexity allows a possible implementation.
Index Terms:
fault-tolerance, distributed systems, automatic self-stabilization, fully asynchronous message passing system, superimposition.
Citation:
Olivier Flauzac, Vincent Villain, "An Implementable Dynamic Automatic Self-Stabilizing Protocol," ispan, pp.91, 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), 1997