𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Self-stabilization with path algebra

✍ Scribed by Bertrand Ducourthial; Sébastien Tixeuil

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
202 KB
Volume
293
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Self-stabilizing protocols can resist transient failures and guarantee system recovery in a ÿnite time. We highlight the connexion between the formalism of self-stabilizing distributed systems and the formalism of generalized path algebra and asynchronous iterations with delay. We use the later to prove that a local condition on locally executed algorithm (being a strictly idempotent r-operator) ensures self-stabilization of the global system. As a result, a parametrized distributed algorithm applicable to any directed graph topology is proposed, and the function parameter of our algorithm is instantiated to produce distributed algorithms for both fundamental and high-level applications. Due to fault resilience properties of our algorithm, the resulting protocols are self-stabilizing at no additional cost.

📜 SIMILAR VOLUMES

Scalable Self-Stabilization
Scalable Self-Stabilization
✍ Sukumar Ghosh; Xin He 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 232 KB

This paper presents a methodology for a synchronous non-reactive distributed system on a tree topology to stabilize from a k-faulty configuration in a time independent of the size n of the system. In the proposed methodology, processes first measure and compare the sizes of the faulty regions, and t