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 using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set {1, . . . , L}, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Two main efficiency measures of a rendezvous algorithm's performance are its time (the number of rounds until the meeting) and its cost (the combined number of edge traversals by both agents). 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. Indeed, this is a lower bound on both the time and the cost of rendezvous. Hence we express the time and cost of rendezvous as functions of an upper bound E on the time of exploration (known to both agents) and 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(E log L). 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 rendezvous algorithm of cost asymptotically E (i.e., of cost E+o(E)) must have time Ω(EL). On the other hand, we show that any rendezvous algorithm with time complexity O(E log L) must have cost Ω(E log L). Moreover, while our algorithms work for arbitrary connected graphs and arbitrary starting times of the agents, these lower bounds hold * Partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. even in a scenario that is very favorable for potential rendezvous algorithms, i.e., for oriented rings of known size and with simultaneous start.
In REF the authors studied tradeoffs between the time of rendezvous and the number of edge traversals by both agents.
Time versus cost tradeoffs for deterministic rendezvous in networks
PODC '14
Computer Science