| 学籍番号 | 90408053 | 所属研究室 | 藤重研 |
| 氏名 | 向 井 友 浩 | ||
| タイトル | 分散システムにおけるビザンチンコテリーについて | ||
|
(1)序論 ビザンチンコテリー\cQとは極小性，b弾性，b一貫性の３つの性質をみたす有限集合Uの部分集合族である．これは互いに通信しながら自律的に動作する計算主体であるノードと，それらを接続する通信リンクによって構成される分散システムにおける相互排除問題解決のために提案されたものである． 本論文では，ビザンチンコテリーの基礎的性質について主に計算量理論の観点から議論する．まず与えられた集合族\cQがb-一貫性をみたすかどうかは，多項式時間で判定できること，また，b-弾性をみたすかどうか判定する問題は，たとえ\cQがb-一貫性をみたしても，CoNP完全であることを示す．次にビザンチンコテリーの極優性判定問題とコテリーの極優性判定問題が互いに多項式時間で還元できることを示す．コテリー\cQの極優性判定問題が多項式時間で可能であるかどうか未だに未解決であり現存のところ，m^{o(log m)}時間でできることが知られている[1]．ただしm = |\cQ|とする．このことにより，ビザンチンコテリー\cQの極優性もm^{o(log m)}時間でできることが分かる．また，この系として与えられたビザンチンコテリーの極優化も準多項式時間で可能であることも示す．最終に|U| >= 6b+2において，任意の極優ビザンチンコテリーを他の極優ビザンチンコテリーに移す方法を提案し，この方法に基づいて，すべての極優ビザンチンコテリーを多項式時間で列挙するアルゴリズムを与える． (2)用語の定義 ノードの全体集合をU，その要素数をnとする．コテリーとは，以下の2つの条件を満たす集合族\cQのことである． 極小性(minimality):任意のQ_{1},Q_{2}(\in \cQ)に対して， Q_{1} \not \subseteq Q_{2}かつQ_{1} \not \supseteq Q_{2}であること． 一貫性(consistency):任意の２つの集合 Q_{1},Q_{2} (\in \cQ)に対して Q_{1} \cap Q_{2} \neq \emptysetであること． 集合族\cQ \subseteq 2^{U}が極小性に加え，以下の2つの条件を満たすときb-マスキングコテリーと呼ばれる． b-弾性(b-resilience):|B| = bである任意のB( \subseteq U) に対してQ \cap B = \emptysetとなるようなQ \in \cQが存在する． b-一貫性(b-consistency):任意の2つの集合Q_{i},Q_{j} \in \cQ が|Q_{i} \cap Q_{j}| >= 2b+1を満たす． 定義1 \cQ,\cQ'をU上の2つの異なるb-マスキングコテリーとする．任意のQ \in \cQに対して，Q' \subseteq QとなるようなQ' \in \cQ'が存在すれば，\cQ'は \cQを優越(dominate)していると呼び，\cQ' \succ \cQと記す．\cQ' \succ \cQとなる\cQ'が存在しないとき，\cQを極優(nondominated;ND)b-マスキングコテリーと呼ぶ． (3)ビザンチンコテリーの基礎的性質 集合族\cQが与えられたとき，それがb-マスキングコテリーかどうかを調べる判定問題について考える．b-一貫性については，定義に従って任意の対Q,Q` \in \cQに対して，|Q \cap Q`| >= 2b+1を判定すればよいので次の結果を得る． 定理1 集合族\cQ \subseteq 2^{U}がb-一貫性をみたすかどうかO(nm^{2})時間で 判定できる．ただし，n = |U|，m = |\cQ|とする． b-弾性は，定義通りに判定すると|B| = bである集合B \subseteq UはO(n^{b})個存在するため，bが一般の場合，指数時間必要なことが分かる．従って，他の方法を考えなければならないのであるが，次のような否定的な結果を得ることができる． 定理2 集合族\cQ \subseteq 2^{U}がb-弾性を満たすかどうか判定する問題は，たとえ，\cQがb-一貫性をみたしても，CoNP完全である． (4)ビザンチンコテリーの極優性判定問題 集合族\cQ \subseteq 2^{U}と非負整数bに対して， Tr_{b}( \cQ) = min{T \subseteq U | |T \cap Q| >= 2b+1,for all Q \in \cQ}とする． 定理3 b-マスキングコテリー\cQが極優である必要十分条件は \cQ = Tr_{b}( \cQ)を満たすことである． 最後に，この特徴付けをうまく応用することにより，次の結果を得る． 定理4 n >= 6b+2において，任意の極優b-マスキングコテリー \cQは他の任意の極優b-マスキングコテリー\cQ'に移ることができる． 参考文献 [1] M. L. Fredman, L. Khachiyan, On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms, 21 (1996) 618-628. [2] D. Malkhi, M. K. Reiter, Byzantine quorum systems. Distributed Computing, 11(4) (1998) 203-213. [3] D. Malkhi, M. K. Reiter, Surviable consensus objects. Seventeenth IEEE Symposium on Reliable Distributed System (SRDS), (1998) 271-279. [4] D. Malkhi, Quorum systems.AT&T Labs-Research, (1999). |
|||