Timed Uniform Atomic Broadcast in Presence of Crash and Timing Faults

Taisuke IZUMI  Toshimitsu MASUZAWA  

IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.1   pp.72-81
Publication Date: 2005/01/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.1.72
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
timed atomic broadcast,  fault tolerance,  timing fault,  crash fault,  

Full Text: PDF>>
Buy this Article

Δ-Timed Atomic Broadcast is the broadcast ensuring that all correct processes deliver the same messages in the same order, and that delivery latency of any message broadcast by any correct process is some predetermined time Δ or less. In this paper, we propose a Δ-timed atomic broadcast algorithm in a synchronous system where communication delay is bounded by a known constant d and processes suffer both crash faults and timing faults. The proposed algorithm can tolerate fc crash faults and ft timing faults as long as at least ft + 1 processes are correct, and its maximum delivery latency Δ is (2f' + 7)d where f' is the actual number of (crash or timing) faulty processes. That is, the algorithm attains the early-delivery in the sense that its delivery latency depends on the actual number of faults rather than the maximum number of faults that the algorithm can tolerate. Moreover, the algorithm has a distinct advantage of guaranteeing that timing-faulty processes also deliver the same messages in the same order as the correct processes (Uniformity). We also investigate the maximum number of faulty processes that can be tolerated. We show that no Δ-timed atomic broadcast algorithm can tolerate ft timing faults, if at most ft processes are correct. The impossibility result implies that the proposed algorithm achieves the maximum fault-resilience with respect to the number of faulty processes.