Timed Atomic Broadcast Resiliet to Multiple Timing Faults

概要

論文の詳細を見る
Abstract Δ-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. This paper proposes a Δ-timed atomic broadcast algorithm in a partially synchronous system where communication delay is bounded (in the range of [d-u,d] where d and u are known constants). The proposed algorithm can tolerate f_c crash faults and [(n-f_c)/2] -1 timing-faults, where n is the number of processes in the system. Moreover, the algorithm has a distinct advantage of guaranteeing that timingfaulty processes also delivers the same messages in the same order as the correct processes. We also investigate the maximum number of faulty processes that can be tolerated. We show that no timed atomic broadcast algorithm can tolerate f_c crash faults and ft timing faults, if [(n-f_c)]/2 [<!_]f_t holds. The impossibility result implies that the proposed algorithm achieves the maximum resilience to both crash and timing faults.
一般社団法人情報処理学会の論文
2003-09-19