How to meet in anonymous network
How to meet in anonymous network
复制标题
DOI：
10.1016/j.tcs.2008.02.010
复制
发表时间：
2006-07
期刊：
影响因子：
--
通讯作者：
D. Kowalski;Adam Malinowski
中科院分区：
文献类型：
--
作者：
D. Kowalski;Adam Malinowski
一组k个移动的代理具有不同的标识符，并位于一个未知的匿名连接网络的节点，必须满足在某个节点。我们发现，这个收集问题是没有比它的特殊情况下，k=2，称为会合问题，并设计确定性协议解决会合问题与任意启动环和一般网络。性能的度量是从最后一个代理启动到实现会合的步骤数。对于环，我们设计了一个不经意的协议，成本为O（nlog），其中n是网络的大小和是参与代理的最小标签。由于[A. Dessmark，P. Fraigniaud，D. Kowalski，A. Pelc，Deterministic rendezvous in graphs，Apriumica 46（2006）69-96].对于一般的网络，我们给出了一个协议，其代价多项式为n和log n，与启动时间的最大差τ无关，它肯定地回答了[A. Dessmark，P. Fraigniaud，D. Kowalski，A. Pelc，Deterministic rendezvous in graphs，Apriumica 46（2006）69-96].
A set of k mobile agents with distinct identifiers and located in nodes of an unknown anonymous connected network, have to meet at some node. We show that this gathering problem is no harder than its special case for k=2, called the rendezvous problem, and design deterministic protocols solving the rendezvous problem with arbitrary startups in rings and in general networks. The measure of performance is the number of steps since the startup of the last agent until the rendezvous is achieved. For rings we design an oblivious protocol with cost O(nlogℓ), where n is the size of the network and ℓ is the minimum label of participating agents. This result is asymptotically optimal due to the lower bound showed by [A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc, Deterministic rendezvous in graphs, Algorithmica 46 (2006) 69–96]. For general networks we show a protocol with cost polynomial in n and logℓ, independent of the maximum difference τ of startup times, which answers in the affirmative the open question by [A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc, Deterministic rendezvous in graphs, Algorithmica 46 (2006) 69–96].