Timed Uniform Atomic Broadcast in Presence of Crash and Timing Faults(<Special Section>Foundations of Computer Science)

スポンサーリンク

概要

• 論文の詳細を見る

• Δ-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.

• 社団法人電子情報通信学会の論文
• 2005-01-01

著者

• Izumi Taisuke

  The Graduate School Of Information Science And Technology Osaka University

• MASUZAWA Toshimitsu

  the Graduate School of Information Science and Technology, Osaka University

• Masuzawa Toshimitsu

  Nara Institute Of Sciences And Technology

• Masuzawa Toshimitsu

  The Graduate School Of Information Science And Technology Osaka University

関連論文

• Fault-Tolerant and Self-Stabilizing Protocols Using an Unreliable Failure Detector
• Timed Uniform Atomic Broadcast in Presence of Crash and Timing Faults(Foundations of Computer Science)
• Wait-Free Linearizable Distributed Shared Memory
• Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model
• High-Level Synthesis for Weakly Testable Data Paths(Special Issue on Test and Diagnosis of VLSI)
• A Simple Parallel Algorithm for the Medial Axis Transform (Special Issue on Architectures Algorithms and Networks for Massively parallel Computing)
• A Parallel Method for the Prefix Convex Hulls Problem
• Distributed Leader Election on Chordal Ring Networks
• Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model(Parallel and Distributed Computing,Foundations of Computer Science)
• Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
• Fault-Tolerance of Distributed Algorithms : Self-Stabilization and Wait-Freedom(Special Issue on Algorithm Engineering : Surveys)
• A Non-scan DFT Method at Register-Transfer Level to Achieve 100% Fault Efficiency (特集:システムLSIの設計技術と設計自動化)
• Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集 並列処理) -- (並列・分散アルゴリズム)
• Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System(Special Section on Discrete Mathematics and Its Applications)

もっと見る 閉じる

スポンサーリンク