The cost of probabilistic agreement in oblivious robot networks
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we look at the time complexity of two agreement problems in networks of oblivious mobile robots, namely, at the gathering and scattering problems. Given a set of robots with arbitrary initial locations and no initial agreement on a global coordinate system, gathering requires that all robots reach the exact same but not predetermined location. In contrast, scattering requires that no two robots share the same location. These two abstractions are fundamental coordination problems in cooperative mobile robotics. Oblivious solutions are appealing for self-stabilization since they are self-stabilizing at no extra cost. As neither gathering nor scattering can be solved deterministically under arbitrary schedulers, probabilistic solutions have been proposed recently. The contribution of this paper is twofold. First, we propose a detailed time complexity analysis of a modified probabilistic gathering algorithm. Using Markov chains tools and additional assumptions on the environment, we prove that the convergence time of gathering can be reduced from O(n^2) (the best known bound) to O(1) or O(logn・log(logn)), depending on the model of multiplicity detection. Second, using the same technique, we prove that scattering can also be achieved in fault-free systems with the same bounds.
- 2010-05-16
論文 | ランダム
- 24pZF-1 不安定核電子散乱実験のための自己閉じ込め型標的(SCRIT)の開発(実験核物理領域,領域I,ビーム物理領域合同招待講演,実験核物理領域)
- 労働者保護の有期労働契約法制の見直しを求める意見書--有期労働契約研究会「報告書」に対して
- 保育制度・施策に関する自治体の意見書
- 平成22年度に本協会[日本私立短期大学協会]が文部科学省等へ提出した主な意見書等
- Induction of metamorphosis in the sand dollar Peronella japonica by thyroid hormones