| Presentation | 2005/6/10 On Solvability of One-Step Consensus Taisuke IZUMI, Toshimitsu MASUZAWA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | While any fault-tolerant asynchronous consensus algorithm requires two communication steps even in failure-free executions, it is known that we can construct the algorithm terminating in one step for some good inputs (e.g. all processes propose a same value). In this paper, we present the necessary and sufficient constraint for the set of inputs for which we can construct the asynchronous consensus algorithm terminating in one step. Our investigation is based on the notion of the condition-based approach: it introduces conditions on input vectors to specify subsets of all possible input vectors and condition-based algorithms can circumvent some impossibility if the actual input vector satisfy a particular condition. More interestingly, conditions treated in this paper are adaptive. That is, we consider hierarchical sequences of conditions whose k-th condition is the set of input vector for which the consensus can be solved in one step even if at most k processes crash. The necessary and sufficient constraint we propose in this paper is one for such condition sequences. In addition, we present several instances of the sufficient condition sequences. Compared with existing constraint for inputs (i.e. all processes propose a same value), all of these instances are more relaxed. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Uniform consensus / Fault tolerance / Crash fault / Condition-based approach |
| Paper # | DC2005-8 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2005/6/10(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) | On Solvability of One-Step Consensus |
| Sub Title (in English) | |
| Keyword(1) | Uniform consensus |
| Keyword(2) | Fault tolerance |
| Keyword(3) | Crash fault |
| Keyword(4) | Condition-based approach |
| 1st Author's Name | Taisuke IZUMI |
| 1st Author's Affiliation | Graduate School of Information Science and Technology, Osaka University() |
| 2nd Author's Name | Toshimitsu MASUZAWA |
| 2nd Author's Affiliation | Graduate School of Information Science and Technology, Osaka University |
| Date | 2005/6/10 |
| Paper # | DC2005-8 |
| Volume (vol) | vol.105 |
| Number (no) | 123 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |