|
Published Articles >> Table of Contents >> Abstract
2004 International Conference on Dependable Systems and Networks (DSN'04)
p. 243
Timed Uniform Consensus Resilient to Crash and Timing Faults
Taisuke Izumi, Osaka University, Japan
Akinori Saitoh, Osaka University, Japan
Toshimitsu Masuzawa, Osaka University, Japan
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DSN.2004.1311894
Send link to a friend
| Abstract |
|
Δ-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: The correct process terminates its execution within a constant time Δ (Δ-timeliness), and no two processes decide differently (Uniformity). In this paper, we consider the Δ-timed uniform consensus problem in presence of f{t} crash processes and f{c} timing-faulty processes. This paper proposes a Δ-timed uniform consensus algorithms. The proposed algorithm is adaptive in the following sense: It solves the Δ-timed uniform consensus when at least f{t} + 1 correct processes exist in the system. If the system has less than f{t} + 1 correct processes, the algorithm cannot solve the Δ-timed uniform consensus. However, as long as f{t} + 1 processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ-timed uniform consensus algorithm tolerating up to f{t} timing-faulty processes requires that the system has at least f{t} + 1 correct processes. This impossibility result implies that the proposed algorithm attains the maximal resilience about the number of faulty processes. We also show that any Δ-timed uniform consensus algorithm tolerating up to f{t} timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than f{t} + 1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.
|
 Additional Information
|
Citation:
Taisuke Izumi, Akinori Saitoh, Toshimitsu Masuzawa,
"Timed Uniform Consensus Resilient to Crash and Timing Faults,"
dsn,
p. 243,
2004 International Conference on Dependable Systems and Networks (DSN'04),
2004
|
|
