A Self-Stabilizing Distributed Algorithm for 5-Spanner

H. Kakugawa and T. Masuzawa (Japan)


self-stabilization, distributed algorithm, spanner, fault tolerant system


Self-stabilization is a theoretical framework of non masking fault-tolerant distributed algorithms. A self stabilizing system tolerates any kind and any finite num ber of transient faults, such as message loss, memory cor ruption, and topology change. Because message loss and topology change occur so frequently in mobile ad hoc net works, distributed algorithms on them should tolerate such events. In this paper, we propose a self-stabilizing dis tributed algorithm for computing a 5-spanner, which can be used, for example, as a basis for computing virtual back bone or routing in mobile ad hoc networks.

Important Links:

Go Back