Randomized Rendezvous of Multiple Mobile Agents in Anonymous Unidirectional Ring Networks

摘要

We consider the rendezvous problem of multiple (mobile) agents in anonymous unidirectional ring net­works under the constraint that each agent knows neither the number of nodes nor agents. First, we prove for any (small) constant p(0 < p ≤ 1) that there exists no randomized algorithm that solves, with probability p, the ren­dezvous problem with (terminal) detection. For this reason, we consider the relaxed rendezvous problem, called the rendezvous problem without detection that does not require termination detection. We prove that there exists no randomized algorithm that solves, with probability 1, the rendezvous problem without detection. For the remaining cases, we show the possibility, that is, we propose a randomized algorithm that solves, with any given constant probability p(0 < p ≤ 1), the rendezvous problem without detection.%本稿では，匿名単方向リングネットワークにおけるモバイルエージェント集合問題について考察する．まず，エージェントがノード数とエージェント数を知らないとき，停止要求を課す集合問題を確率p（0＜p≦1）で解く乱択アルゴリズムが存在しないことを示す．そこで，停止要求を課さないように緩和した集合問題を考える．まず，停止要求を課さない集合問題を確率1で解く乱択アルゴリズムが存在しないことを示す．次に，停止要求を課さない集合問題を確率p（0＜p＜1）で解く乱択アルゴリズムを提案する．