2024-03-28T17:19:15Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000904162023-04-27T10:00:04Z01164:02592:07086:07087
一般のネットワーク上の移動ビザンチン合意問題についてMobile Byzantine Agreement Problem in Arbitrary Networksjpnhttp://id.nii.ac.jp/1001/00090399/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=90416&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of Japan九州大学工学部電気情報工学科九州大学大学院システム情報科学研究院九州大学大学院システム情報科学研究院九州大学大学院システム情報科学研究院佐々木徹山内由紀子来嶋秀治山下雅史アルゴリズムに関係なく任意の振る舞いをするようなビザンチン故障をしているプロセスが存在する分散システムにおいて,全プロセスで合意を形成する問題をビザンチン合意問題という.故障プロセス集合が時間ごとに変化する移動ビザンチン合意問題では,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}の場合の分散アルゴリズムを与える.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」.AN1009593X研究報告アルゴリズム(AL)2013-AL-14312182013-02-222013-02-15