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

遍历理论在分布式算法中的应用

• 批准号: 14740077
• 负责人: 中田 寿夫
• 金额: $ 1.79万
• 依托单位: Fukuoka University of Education
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14740077/
• 关键词: 分散アルゴリズム; ランダムウォーク; カップリング; 差分方程式; 1次元ランダムウォーク; ランダム環境; マルコフ連鎖; 再帰性; 正規分布; グラフ; ネットワーク; アルゴリズム; 最大パス; 確率分布の裾の評価; 最大値の分布; LSIの設計

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

This year, we will study the theory of theory in the current year. In 1990, the specific Herman training program promoted the spread of accuracy, assurance rate, and Herman assurance rate. The average time spent on mathematics was better than that of others. I don't know what to do. I don't know. I don't know. An example of a case study is that of Herman officials. We are looking forward to making specific requests and waiting for more information about your needs. In this paper, we discuss the application of computer, computer, and so on. At the same time (after the introduction of this article), Professor CNRS

项目成果

T.Nakata: "A remark on birth-and-death chains in a random environment"Bulletin of Fukuoka University of Education.III.. 53. 1-6 (2004)

T.Nakata：“关于随机环境中的生死链的评论”福冈教育大学公告.III.. 53. 1-6 (2004)

Ando, Yamashita, Nakata, Matsunaga: "Longest Path Problem and Its Application to Delay Analysis of Logical Circuits"Proc. ACM/IEEE International Workshop TAU'02. 134-139 (2002)

Ando、Yamashita、Nakata、Matsunaga：“最长路径问题及其在逻辑电路延迟分析中的应用”Proc。

On the expected time for Herman's probabilistic self-stabilizing algorithm

• DOI: 10.1016/j.tcs.2005.05.022
• 发表时间: 2004-08
• 期刊: Theor. Comput. Sci.
• 作者: Toshio Nakata