Adaptive timeliness of consensus in presence of crash and timing faults

概要

論文の詳細を見る
The Δ-timed uniform consensus is a stronger variant of the traditional consensusand it satisfies the following additional property: Every correct process terminatesits execution within a constant time Δ (Δ-timeliness), and no two processes decidedifferently (Uniformity). In this paper, we consider the Δ-timed uniform consensusproblem in presence of fc crash processes and ft timing-faulty processes, and proposea Δ-timed uniform consensus algorithm. The proposed algorithm is adaptive inthe following sense: It solves the Δ-timed uniform consensus when at least ft + 1correct processes exist in the system. If the system has less than ft + 1 correctprocesses, the algorithm cannot solve the Δ-timed uniform consensus. However, aslong as ft + 1 processes are non-crashed, the algorithm solves (non-timed) uniformconsensus. We also investigate the maximum number of faulty processes that canbe tolerated. We show that any Δ-timed uniform consensus algorithm toleratingup to ft timing-faulty processes requires that the system has at least ft + 1 correctprocesses. This impossibility result implies that the proposed algorithm attains themaximum resilience about the number of faulty processes. We also show that anyΔ-timed uniform consensus algorithm tolerating up to ft timing-faulty processescannot solve the (non-timed) uniform consensus when the system has less thanft + 1 non-crashed processes. This impossibility result implies that our algorithmattains the maximum adaptiveness.
Elsevier BVの論文
2007-06-00

Adaptive timeliness of consensus in presence of crash and timing faults

スポンサーリンク

概要

Elsevier BV | 論文

スポンサーリンク