一般のネットワーク上の移動ビザンチン合意問題について

• Item type: SIG Technical Reports(1)
• 公開日: 2013-02-22
• タイトル: 一般のネットワーク上の移動ビザンチン合意問題について
• タイトル / 言語: en
• タイトル: Mobile Byzantine Agreement Problem in Arbitrary Networks
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学工学部電気情報工学科
• 著者所属: 九州大学大学院システム情報科学研究院
• 著者所属: 九州大学大学院システム情報科学研究院
• 著者所属: 九州大学大学院システム情報科学研究院
• 著者名: 佐々木徹; 山内由紀子; 来嶋秀治; 山下雅史
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: アルゴリズムに関係なく任意の振る舞いをするようなビザンチン故障をしているプロセスが存在する分散システムにおいて，全プロセスで合意を形成する問題をビザンチン合意問題という．故障プロセス集合が時間ごとに変化する移動ビザンチン合意問題では，Garay(1994)により，n > 6tの場合の完全ネットワークにおける分散アルゴリズムが提案された．ただし，nは全プロセス数，tは故障プロセス数とする．本研究では，一般のネットワークでの移動ビザンチン合意問題を解くアルゴリズムとその上下界についてネットワークの構造に着目しながら考える．まず，点連結度がdの通信ネットワークG上での移動ビザンチン合意問題は，n > 6tかつd > 4tでないと解けないことを示す．次に，一部のプロセスと通信リンクを持たないネットワークの例として完全k部グラフを考え，n-3(n/k-1) > 6tの場合の分散アルゴリズムを与える．また，直径の大きさがnとdによって決まるリングのべき乗Cd/2nではd > min{8t, n+4t-2/2}の場合の分散アルゴリズムを与える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Byzantine agreement problem is to make processes in a distributed system agree on their proposed values even in the presence of Byzantine faults. Garay (1994) proposed the mobile Byzantine agreement problem where the set of Byzantine processes continuously changes, and presented a distributed algorithm in a complete network with n > 6t processes where t is the number of faulty processes and n is the number of entire processes. In this paper, we consider the mobile Byzantine agreement problem in an arbitrary network. We first show that the mobile Byzantine agreement is unsolvable unless n > 6t and d > 4t where d is the diameter of the network. Then, we present two distributed algorithms. The first algorithm considers complete k-partite graph with n-3(n/k-1) > 6t where each process does not have direct communication link to some other processes. The other algorithm considers d/2-th power of a cycle graph with d > min{8t, n+4t-2/2} where the diameter of the graph is 「n-1/d」.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2013-AL-143, 号 12, p. 1-8, 発行日 2013-02-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会