極大局所リーダー選挙問題を解く分散アルゴリズム

摘要

分散システムとはプロセスと通信リンクの集合から構成されるシステムである．本稿で札独立点集合問題とリーダー選挙問題を特別な場合として含むd-局所リーダー選挙問題を扱う．局所リーダー選挙問題とは，あるd≧1に対して，距離d内にあるプロセスは同時にリーダーになってはならない，という問題である．d＝1の時は独立点集合問題であり，d＝D（ネットワーク直径）の時はリーダー選挙問題に対応している．この問題は，非同期匿名ネットワークの下では問題を解く決定性のアルゴリズムが存在しないことが示されている．本稿では各プロセスが固有の識別子を持つ場合にd＝2に対して，極大2－局所リーダー選挙問題を解く分散アルゴリズムを提案し，その正当性を示す．