Time versus cost tradeoffs for deterministic rendezvous in networks
Time versus cost tradeoffs for deterministic rendezvous in networks
复制标题
网络中确定性交会的时间与成本权衡
作者：
Avery Miller;A. Pelc
两个移动的代理，在可能不同的时间从网络的不同节点出发，必须在同一节点相遇。这个问题被称为会合。代理在同步轮中移动。每个代理具有来自集合$${1，ldots，L}$${1，.，L}的不同整数标签。交会的两个主要效率度量是其时间（直到会议的轮数）和其成本（边缘遍历的总数）。我们研究这两种措施之间的权衡。网络中会合的时间和成本的一个自然基准是访问网络中所有节点所需的边遍历次数，称为探索时间。因此，我们表示的时间和成本的交会作为函数的上限E的探索时间（其中E和相应的探索过程是已知的两个代理）和标签空间的大小L。我们提出了两个自然会合算法。廉价算法的成本为O（E）（事实上，对于代理同时启动的模型，该算法的一个版本的成本正好为E），时间为O（EL）。快速算法的时间和成本都是$$O（Elog L）$$O（Elog L）。我们的主要贡献是下界显示，也许令人惊讶的是，这两种算法捕获的时间和成本的交会几乎紧密之间的权衡。我们证明，任何确定性的会合算法的成本渐近E（即，成本$$E + o（E）$$E + o（E））必须具有时间$$varOmega（EL）$$Ω（EL）。另一方面，我们表明，任何确定性交会算法的时间复杂度为$$O（Elog L）$$O（ElogL）必须有成本$$varOmega（Elog L）$$Ω（ElogL）。
Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds. Each agent has a distinct integer label from the set $${1,ldots ,L}$${1,…,L}. Two main efficiency measures of rendezvous are its time (the number of rounds until the meeting) and its cost (the total number of edge traversals). We investigate tradeoffs between these two measures. A natural benchmark for both time and cost of rendezvous in a network is the number of edge traversals needed for visiting all nodes of the network, called the exploration time. Hence we express the time and cost of rendezvous as functions of an upper bound E on the time of exploration (where E and a corresponding exploration procedure are known to both agents) and of the size L of the label space. We present two natural rendezvous algorithms. Algorithm Cheap has cost O(E) (and, in fact, a version of this algorithm for the model where the agents start simultaneously has cost exactly E) and time O(EL). Algorithm Fast has both time and cost $$O(Elog L)$$O(ElogL). Our main contributions are lower bounds showing that, perhaps surprisingly, these two algorithms capture the tradeoffs between time and cost of rendezvous almost tightly. We show that any deterministic rendezvous algorithm of cost asymptotically E (i.e., of cost $$E+o(E)$$E+o(E)) must have time $$varOmega (EL)$$Ω(EL). On the other hand, we show that any deterministic rendezvous algorithm with time complexity $$O(Elog L)$$O(ElogL) must have cost $$varOmega (Elog L)$$Ω(ElogL).
使用对数内存进行树探索
影响因子：
1.3
作者：
Ambühl C
通讯作者：
Ambühl C