| Presentation | 2004/4/9 Timed Uniform Consensus Protocol Tolerating Crash and Timing Faults Taisuke IZUMI, Akinori SAITOH, Toshimitsu MASUZAWA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Δ-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 alive, 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Timed uniform consensus / Fault tolerance / Timing fault / Crash fault |
| Paper # | CPSY2004-7,DC2004-7 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2004/4/9(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Dependable Computing (DC) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Timed Uniform Consensus Protocol Tolerating Crash and Timing Faults |
| Sub Title (in English) | |
| Keyword(1) | Timed uniform consensus |
| Keyword(2) | Fault tolerance |
| Keyword(3) | Timing fault |
| Keyword(4) | Crash fault |
| 1st Author's Name | Taisuke IZUMI |
| 1st Author's Affiliation | Graduate School of Information Science and Technology, Osaka University() |
| 2nd Author's Name | Akinori SAITOH |
| 2nd Author's Affiliation | Graduate School of Information Science and Technology, Osaka University |
| 3rd Author's Name | Toshimitsu MASUZAWA |
| 3rd Author's Affiliation | Graduate School of Information Science and Technology, Osaka University |
| Date | 2004/4/9 |
| Paper # | CPSY2004-7,DC2004-7 |
| Volume (vol) | vol.104 |
| Number (no) | 13 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |