Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent›Rendezvous

Rendezvous

Two agents start at different nodes of an unknown graph and must meet; how long does it take, and how much memory or symmetry breaking does it need?

Problem statement and measuresexpand

Two mobile agents start at different nodes of an unknown connected port-labelled graph. In the synchronous model they must be at the same node in the same round; in the asynchronous model an adversary controls their speeds and they may also meet inside an edge. Agents are either labelled (distinct labels from \(\{1,\dots,L\}\); \(\lambda\) is the smaller label) or anonymous. They may start at different times; \(\tau\) is the delay. Time is the number of rounds from the start of the later agent (synchronous) or the total number of moves, that is edge traversals (asynchronous cost). Memory is bits per agent.

Measures: Time, rounds after the later agent starts (synchronous); edge traversals (asynchronous); Memory, bits per agent.

no assumptions›+ static graph, + undirected›+ finite graph›+ distinct IDs (eponymous)›+ synchronous

Labelled agents, arbitrary finite graphs

standard settingdraft

Time: polynomial gapMemory: unknown

Polynomial in \(n\) and \(\log \lambda\) and independent of the delay, but far from the known lower bounds.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Graph sizefinite+Identifiersdistinct identifiers (eponymous): agents have pairwise distinct identifiers+Timingsynchronous rounds

Not assumed

Startarbitrary delay between the two startsTopologyarbitrary connected graph

Formal definitions of this setting

Graph dynamics: static graph: \(G_t=G\) for all \(t\): the edge set never changes.
Edge direction: undirected: \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
Graph size: finite graph: \(G\) has finitely many nodes.
Identifiers: distinct IDs (eponymous): Distinct identifiers (eponymous agents): the label function \(\mathrm{id}:\{1,\dots,k\}\to\{1,\dots,L\}\) is injective; usually \(L=k^{O(1)}\), so a label takes \(O(\log k)\) bits.
Timing: synchronous: Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
Start: any delay: An adversary wakes the agents at times \(t_1\) and \(t_2\); the delay \(\tau=|t_1-t_2|\) is unknown.
Topology: any topology: \(G\) is any connected graph in the class allowed by the other axes.

What is known

Time · rounds after the later agent starts (synchronous); edge traversals (asynchronous)

polynomial gap

\(\tilde O(n^5\log \lambda)\) versus \(\Omega(n^2+\log \lambda)\).

lower bounds

\(\Omega(n^2)\) Dessmark et al. 2006

bottleneckexploration

holds when

Theorem 4.4: for all \(n\) and all pairs of labels, a regular graph made of two cliques of \(n/2\) nodes joined by two swapped edges, ports equal at both ends of each edge
holds even with simultaneous start

\(\Omega(\log \lambda)\) Dessmark et al. 2006

bottlenecksymmetry breaking

holds when

the two-node graph, agents at both ends, simultaneous start: with fewer steps than label bits two labels produce the same move/stay sequence
extends to trees (Theorem 2.3)

introductory

\(O(n^5\sqrt{\tau\log \lambda}\,\log n+n^{10}\log^2 n\log \lambda)\)

Dessmark et al. 2006

memory unbounded; local computation free

current best

\(\tilde O(n^5\log \lambda)\)

Ta-Shma & Zwick 2014

Memory · bits per agent

unknown

Memory is unbounded in these algorithms.

lower boundnone known

introductory—

current best—

Results, in order of publication

Dessmark et al. 2006 introductory

Time \(O(n^5\sqrt{\tau\log \lambda}\,\log n+n^{10}\log^2 n\log \lambda)\)

memory unbounded; local computation free

Theorem 4.3: polynomial in \(n\), \(\tau\) and \(\log\lambda\). Not constructive in the computational sense: each agent finds, by exhaustive local search, a combinatorial object whose existence is proved by the probabilistic method; only moves are counted.

Kowalski & Malinowski 2008 also

Time \(O(\log^3 \lambda+n^{15}\log^{12}n)\)

backtracking: the agent learns the port by which it entered

First bound independent of \(\tau\) (as stated in Pelc 2019); needs backtracking (as stated in Ta-Shma & Zwick 2014).

Ta-Shma & Zwick 2014 current best

Time \(\tilde O(n^5\log \lambda)\)

Independent of \(\tau\) and needs no backtracking, but not explicit: it relies on universal traversal sequences that are only known to exist. Checked in the paper. (Xin 2007 wrongly says it uses backtracking.)

Open questions

Find an optimal-time synchronous rendezvous algorithm for labelled agents in arbitrary graphs (open problem of Pelc 2019).

Notes

\(\ell\) in Ta-Shma & Zwick 2014 is the length of the shorter label, our \(\log \lambda\). Checked against the full text of Dessmark et al. 2006: there agents know only their own label, learn the entry port and the degree at each node, and do not notice crossing inside an edge. With simultaneous start the same paper meets in \(O(d\Delta^{d}\log\lambda)\) rounds in any graph without knowing \(\Delta\) (Theorem 4.1), optimal when \(d\) and \(\Delta\) are bounded. Unverified against the original paper: the bound of Kowalski & Malinowski 2008 (from Pelc 2019); Ta-Shma & Zwick 2014 was read in full.

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.