2024-03-28T19:58:58Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000319062023-04-27T10:00:04Z01164:02592:02627:02629
Timed Atomic Broadcast Resiliet to Multiple Timing FaultsTimed Atomic Broadcast Resiliet to Multiple Timing Faultsjpnhttp://id.nii.ac.jp/1001/00031906/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31906&item_no=1&attribute_id=1&file_no=1Copyright (c) 2003 by the Information Processing Society of JapanGraduate School of Information Science and Technology Osaka UniversityGraduate School of Information Science and Technology Osaka UniversityGraduate School of Information Science and Technology Osaka UniversityTaisuke, IzumiAkinori, SaitohToshimitsu, Masuzawa△-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 timing-faulty 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 f_t 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.△-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 timing-faulty 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 f_t 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.AN1009593X情報処理学会研究報告アルゴリズム(AL)200392(2003-AL-091)35422003-09-192009-06-30