Studies on Self-Stabilizing k-Exclusion Protocols
浮穴学慈 (9751015)
分散システムとは、複数の自律動作するプロセッサと、それらの間の通信リンクからなるネットワークシステムです。
分散システム上で問題を解決するアルゴリズムで終了条件のないものを、分散プロトコルといいます。
システムのどのような初期状況から実行を開始しても、やがて目的とする動作をするようになるプロトコルを、自己安定プロトコルといいます。
従って、自己安定プロトコルは、どのような規模および種類の一時故障に対しても耐性を持ちます。
このような高度な故障耐性を持つ自己安定プロトコルで扱う問題として、k-相互排除問題を選びました。
k-相互排除問題は、排他的に使用される k 個の資源のうちどれか 1 個を使用したいとき、その使用権の競合を解消する問題です。
本論文では、分散システムの一般的なモデルである共有メモリモデルにおいて、k-相互排除問題を解く自己安定プロトコルを提案しました。
なお、本プロトコルでは、k-無待機性を実現しました。
k-相互排除問題における x-無待機性とは、資源を要求するプロセッサが高々 x 個のとき、どのプロセッサもお互いに干渉されることなく資源を獲得できるという性質で、x=k のとき最適です。