WEKO3
アイテム
Condition Adaptation in Synchronous Consensus
https://nitech.repo.nii.ac.jp/records/3572
https://nitech.repo.nii.ac.jp/records/3572f69b8bc7-49f5-4057-8d8e-343b9b8e801d
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
本文_fulltext (155.6 kB)
|
c 2006 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-06-25 | |||||||||||||||
| タイトル | ||||||||||||||||
| タイトル | Condition Adaptation in Synchronous Consensus | |||||||||||||||
| 言語 | en | |||||||||||||||
| 言語 | ||||||||||||||||
| 言語 | eng | |||||||||||||||
| 資源タイプ | ||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||
| 資源タイプ | journal article | |||||||||||||||
| 著者 |
泉, 泰介
× 泉, 泰介
× Masuzawa, Toshimitsu
|
|||||||||||||||
| 著者別名 | ||||||||||||||||
| 姓名 | Izumi, Taisuke | |||||||||||||||
| 言語 | en | |||||||||||||||
| 姓名 | 泉, 泰介 | |||||||||||||||
| 言語 | ja | |||||||||||||||
| 姓名 | イズミ, タイスケ | |||||||||||||||
| 言語 | ja-Kana | |||||||||||||||
| bibliographic_information |
en : IEEE Transactions on Computers 巻 55, 号 7, p. 843-853, 発行日 2006 |
|||||||||||||||
| 出版者 | ||||||||||||||||
| 出版者 | Institute of Electrical and Electronics Engineers | |||||||||||||||
| 言語 | en | |||||||||||||||
| ISSN | ||||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||||
| 収録物識別子 | 0018-9340 | |||||||||||||||
| item_10001_source_id_32 | ||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||
| 収録物識別子 | AA00667762 | |||||||||||||||
| 出版タイプ | ||||||||||||||||
| 出版タイプ | AM | |||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||
| item_10001_relation_34 | ||||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||
| 関連識別子 | http://dx.doi.org/10.1109/TC.2006.99 | |||||||||||||||
| 関連名称 | 10.1109/TC.2006.99 | |||||||||||||||
| 内容記述 | ||||||||||||||||
| 内容記述タイプ | Other | |||||||||||||||
| 内容記述 | The condition-based approach is one of sophisticated methods to overcome several impossibilityresults in distributed consensus problem (e.g., impossibility of fault tolerance inasynchronous consensus, or time complexity lower bounds in synchronous consensus). Itintroduces conditions on input vectors to specify subsets of all possible input vectors to consensusalgorithms, and condition-based algorithms can circumvent the impossibility if actualinput vectors satisfy a particular condition. In this paper, we present a new condition-basedparadigm for synchronous consensus. We newly introduce the concept of adaptation on thetime complexity of condition-based algorithms, and present the adaptive condition-basedapproach to synchronous consensus. In our approach, all possible input vectors are classifiedinto hierarchical conditions according to their difficulty called the legality level. Executiontime of adaptive condition-based algorithms depends on the legality level of input vectors.We propose two adaptive condition-based algorithms for synchronous consensus. Thefirst algorithm requires that the majority of processes are correct, and terminates withinmin{f + 2; t + 1} ? l rounds if l < f, where f and t is the actual and the maximum numbersof faults respectively, and l is the legality level of the input vector. Moreover, thealgorithm terminates in one round if l ? t and f = 0, and terminates within two roundsif l ? f holds. Compared with previous algorithms, this algorithm achieves the best timecomplexity. The second algorithm can tolerate any number of faults, and terminates withinmax{3; min{f + 3; t + 2} ? l} rounds if l < f holds, terminates in one round if l ? t andf = 0, and terminates within three rounds if l ? f holds.Index Terms : distributed algorithm, synchronous system, consensus problem, fault-tolerance,crash fault, condition-based approach, adaptive algorithm | |||||||||||||||
| 言語 | en | |||||||||||||||
