Fault-Tolerant and Self-Stabilizing Protocols Using an Unreliable Failure Detector

Hiroyoshi MATSUI  Michiko INOUE  Toshimitsu MASUZAWA  Hideo FUJIWARA  

IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.10   pp.1831-1840
Publication Date: 2000/10/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithms
distributed algorithms,  self-stabilization,  fault-tolerance,  failure detector,  x-group consensus,  

Full Text: PDF>>
Buy this Article

We investigate possibility of fault-tolerant and self-stabilizing protocols (ftss protocols) using an unreliable failure detector. Our main contribution is (1) to newly introduce k-accuracy of an unreliable failure detector, (2) to show that k-accuracy of a failure detector is necessary for any ftss k-group consensus protocol, and (3) to present three ftss k-group consensus protocols using a k-accurate and weakly complete failure detector under the read/write daemon on complete networks and on (n-k+1)-connected networks, and under the central daemon on complete networks.