木ネットワークにおけるビザンチン故障耐性を有する自己安定辺彩色プロトコル

摘要

自己安定プロトコルは，分散システムが任意の初期状況から実行を開始しても，有限時間内に正しく動作することを保証するプロトユルであり，任意の一時故障に対する耐性を有する。 しかし，永久故障に対する耐性は有しておらず，永久故障に対する耐性を有する自己安定プロトコルの設計開発が望まれている。 本稿では，永久故障モデルとして，ビザンチン故障を対象に，木ネットワークにおいてビザンチン故障耐性を有する自己安定辺彩色プロトコルの可能性について考察する。 本報告ではまず，同時に一つのプロセスしか動作しないCデーモンによるスケジュールを仮定し，システム内のノードの最大次数△に対して△＋1色を用いて彩色する自己安定プロトコルを提案する。 このプロトコルでは故障の影響を故障ノードからの距離が2までのノードに封じ込めている。 また，nをシステム内の総ノード数とするとき，△色を用いた辺彩色では，故障の影響が故障ノードから距離Ω(log n) のノードへ広がることを示す。さらに，同時に複数のプロセスが動作しうるDデーモンを仮定したモデルではビザンチン故障の影響範囲が距離Ω(n) のノードに広がることを示す。