自己安定アルゴリズムの出力変化削減手法

瓦谷 佳祐 (1051034)


インターネット,携帯電話網,高度道路交通システム,多種多様な無線センサネットワークの普及に伴い, 近年,多種多様な計算機システムが相互に連携した大規模かつ複雑な計算機ネットワークが増加している. 個々のシステムを分散システムと見なせば,このような複雑な計算機ネットワークは 多数の分散システムが入出力を介して,相互に連携するシステムと見なすことができる.

分散システムでの重要な問題として故障耐性がよく研究されている. 一般的には,システム中の個々の計算機が故障しても,システム全体としてのはたらきを 維持する,または自律的に回復する性質が故障耐性と呼ばれている. しかし,故障からシステムが復旧する期間には, 個々の計算機で再計算が起こり, システムの外部観測者や計算結果を利用する外部システムへ何らかの影響を 与える可能性がある. 本研究では,耐故障分散システムの相互連携に着目し, 復旧途中にもシステム外部への影響の小さい分散アルゴリズムの設計を目指す.

故障耐性を持つ分散アルゴリズムのひとつに,自己安定アルゴリズムがある. 自己安定アルゴリズムでは,復旧途中に各計算機が管理する外部システムへの出力が 複数回変化する可能性がある. 本研究では,まず,全域木作成問題,極大マッチング問題,極大独立点集合問題に対して, 復旧途中に各計算機が出力を高々1回変化させるのみの自己安定アルゴリズムを 設計できないことを示す. つまり,上記の問題については,外部システムは復旧途中の計算結果の変化を複数回観測する 可能性があることを示す. 次に,本研究では,極大マッチング問題,極大独立点集合問題に対して, 出力変化回数を抑制する自己安定アルゴリズムを提案する. 分散システム中の計算機の数をnとすると,極大マッチング問題に対する既存のアルゴリズムでは, 全ての計算機の出力変化回数の総和はO(n2)であり, 極大独立点集合問題についての出力変化回数の総和はO(n)である. 提案アルゴリズムの出力変化回数の総和はいずれもO(n)である.

極大独立点集合問題に対しては,出力変化回数の計算複雑度に変化がないため, 計算機によるシミュレーション実験を行い, 既存手法と提案手法の出力変化回数を評価した. 実験結果から,提案手法は復旧途中に2回出力変数が変化するプロセスの数を 約95%削減することが分かった.