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›anonymous, + synchronous

Anonymous agents: memory

verified

Time: unknownMemory: tight

Identical agents can meet whenever their positions are not symmetric, and \(\Theta(\log n)\) bits are exactly what it takes.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Graph sizefinite+Timingsynchronous rounds

Not assumed

Identifiersanonymous: all agents are identicalStartarbitrary 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: anonymous: All agents run the same deterministic algorithm on the same input; no agent has a label. Formally the label function is constant: \(\mathrm{id}(a)=\mathrm{id}(b)\) for all agents \(a,b\).
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)

unknown

Not the focus.

lower boundnone known

introductory—

current best—

Memory · bits per agent

tight

\(\Theta(\log n)\) bits.

lower bound

\(\Omega(\log n)\) Czyzowicz et al. 2012

bottlenecksymmetry breaking

holds when

rings
holds even with simultaneous start

introductory—

current best

\(O(\log n)\)

Czyzowicz et al. 2012

Results, in order of publication

Czyzowicz et al. 2012 current best

Memory \(O(\log n)\)

Introductory and current best; any delay; also gives the first polynomial-time computation of a quotient graph.

Open questions

None recorded for this variant.

Notes

Rendezvous is feasible exactly when the two starting nodes have different views.

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.