一般分散計算論

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

生体分子の機能発現から人間世界の選挙に至る広範な領域の問題から領域固有の事由を捨象し，内在する分散計算構造に着目すると，合意計算問題が共通して出現する．この事実に着目し，巨大分散システムを分散計算能力の観点から統一的に理解することが本研究の最終目的である．特に，本研究では，識別子や記憶を持たない構成要素を持たない構成要素から構成され，不安定なゆらぎの下で働く自然分散システムが豊富に有する自律性を，はるかに有利な条件の下で働く人口分散システムに付与することの困難であることの根源的な理由を理解したい．結論として，自然界のゆらぎが一様ランダムであるという仮定の下であるが，上記で説明した根源的理由を以下に示す3つの定理を証明することによって，明らかにすることができた．ただし，分散モデルとして2次元空間上を移動する自律分散ロボットモデルを用い，自律性として自己組織化問題，すなわち自己安定的パターン形成問題を検討した：定理1．決定的匿名ロボットでは，ロボット間の同期の程度と記憶の有無はパターン形成能力に影響を与えない．定理2．故障（ゆらぎ）が一様ランダムであるという条件の下では，匿名で無記憶なロボットの動作は自動的に自己安定的である．定理3．確率的アルゴリズムの導入によって，ロボットシステムは任意の初期状態から任意のパターンを形成できる．これらの定理から，自己組織化には，匿名性，無記憶性，ゆらぎが重要な役割を果たしており，これらは自然分散システムが自然に持っている性質であることから，自然分散システムが自己組織化能力を自然に獲得しているという事情が明確になった．そこで，申請者は，引き続き，3次元空間を移動するロボットに対する検討を進めており，完全同期という限られた条件の下で，記憶が自己組織化に与える影響を検討した．