hide
Free keywords:
-
Abstract:
Two mobile agents having distinct identifiers and located in nodes of an
unknown anonymous connected graph, have to meet at some node of the graph. We
seek fast deterministic algorithms for this rendezvous problem, under two
scenarios: simultaneous startup, when both agents start executing the algorithm
at the same time, and arbitrary startup, when starting times of the agents are
arbitrarily decided by an adversary. The measure of performance of a rendezvous
algorithm is its cost: for a given initial location of agents in a graph, this
is the number of steps since the startup of the later agent until rendezvous is
achieved. We first show that rendezvous can be completed at cost O(n + log l)
on any n-node tree, where l is the smaller of the two identifiers, even with
arbitrary startup. This complexity of the cost cannot be improved for some
trees, even with simultaneous startup. Efficient rendezvous in trees relies on
fast network exploration and cannot be used when the graph contains cycles. We
further study the simplest such network, i.e., the ring. We prove that, with
simultaneous startup, optimal cost of rendezvous on any ring is Θ(D log l),
where D is the initial distance between agents. We also establish bounds on
rendezvous cost in rings with arbitrary startup. For arbitrary connected
graphs, our main contribution is a deterministic rendezvous algorithm with cost
polynomial in n, τ and log l, where τ is the difference between startup times
of the agents. We also show a lower bound Ω (n2) on the cost of rendezvous in
some family of graphs. If simultaneous startup is assumed, we construct a
generic rendezvous algorithm, working for all connected graphs, which is
optimal for the class of graphs of bounded degree, if the initial distance
between agents is bounded.
