エルゴード理論の分散アルゴリズムへの応用

点击翻译按钮获取中文摘要

本年度は、ランダムウォークを応用して分散アルゴリズム理論の研究を行った。具体的には1990年にHermanによって提唱された、確率的分散アルゴリズム、すなわち、Hermanの確率的自己安定アルゴリズムの平均終了時間についての数学的な評価を得た。これまでの自己安定アルゴリズムの研究において、多くのアルゴリズム理論研究者により、決定的アルゴリズムでは実現できない良い性質を持つアルゴリズムとして確率的アルゴリズムが定式化され、さらに、それが確率1で停止する事を示してその有効性が議論されていた。Hermanによる仕事もその一例である。しかし、停止時間の期待値を具体的に求める、あるいはシャープに評価するのは困難とされていた。ここでは、ランダムウォークのカップリングの議論を用いて、その状態の推移をマルコフ連鎖として定式化し、複雑な連鎖を簡単な差分方程式に帰着することに成功したことにより、その平均時間に関しての非自明な評価を得た。国外では、同時期(本報告書の論文よりも僅かに後)にCNRSのFribourg教授のグループ(DISC 2004,LNCS,3274)により、同様の結果が発表されている。彼らの手法は、2000年前後に発見され現在も理論計算機の分野で爆発的に研究されている「パスカップリング」と呼ばれている手法を用いているが、彼らよりも良い評価を与えることになった。