Timed Uniform Atomic Broadcast in Presence of Crash and Timing Faults

摘要

Δ-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 f_c crash faults and f_t timing faults as long as at least f_t + 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 f_t timing faults, if at most f_t processes are correct. The impossibility result implies that the proposed algorithm achieves the maximum fault-resilience with respect to the number of faulty processes.