Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment Property

Yukiko YAMAUCHI  Sayaka KAMEI  Fukuhito OOSHITA  Yoshiaki KATAYAMA  Hirotsugu KAKUGAWA  Toshimitsu MASUZAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.3   pp.451-459
Publication Date: 2009/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.451
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Distributed Cooperation and Agents
Keyword: 
fault-containment,  self-stabilization,  composition,  

Full Text: PDF(370.2KB)
>>Buy this Article


Summary: 
A desired property of large distributed systems is self adaptability against the faults that occur more frequently as the size of the distributed system grows. Self-stabilizing protocols provide autonomous recovery from finite number of transient faults. Fault-containing self-stabilizing protocols promise not only self-stabilization but also containment of faults (quick recovery and small effect) against small number of faults. However, existing composition techniques for self-stabilizing protocols (e.g. fair composition) cannot preserve the fault-containment property when composing fault-containing self-stabilizing protocols. In this paper, we present Recovery Waiting Fault-containing Composition (RWFC) framework that provides a composition of multiple fault-containing self-stabilizing protocols while preserving the fault-containment property of the source protocols.