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. Nodes are anonymous unless a setting gives them node labels: distinct positive integers that an agent reads when it is at the node. 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: polynomial gapMemory: tight

Identical agents can meet whenever their positions are not symmetric, or are symmetric but start with a long enough delay; \(\Theta(\log n)\) bits suffice when the positions are not symmetric.

Assumed (added on the last edge are outlined)

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

Not assumed

Node identifiersanonymous nodesIdentifiersanonymous: 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.
Node identifiers: anonymous nodes: Nodes have no identifiers; an agent at \(v\) sees only \(\deg(v)\) and the port numbers \(1,\dots,\deg(v)\), which are assigned locally and independently at each endpoint of an edge.
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)

polynomial gap

Exponential in \(d\) (Theorem 4.1 of Pelc & Yadav 2019b) against \((n+\tau)^{O(n+\tau)}\); whether a universal algorithm can run in time polynomial in \(n\) and \(\tau\) is open.

lower bound

\(2^{\Omega(d)}\) Pelc & Yadav 2019b

bottlenecksymmetry breaking

holds when

symmetric start nodes at distance \(d\) with a feasible delay, in a graph built from a regular tree whose ports give the agents no information (Theorem 4.1)
for an algorithm that meets for every such start, as a universal algorithm must

introductory—

current best

\((n+\tau)^{O(n+\tau)}\)

Pelc & Yadav 2019b

every feasible start: nonsymmetric nodes with any delay, or symmetric nodes \(u, v\) with delay \(\tau \ge \mathrm{Shrink}(u,v)\)no knowledge of \(n\), \(\tau\) or the start nodes

Memory · bits per agent

tight

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

lower bound

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

bottlenecksymmetry breaking

holds when

rings
holds even with simultaneous start

introductory—

current best

\(O(\log n)\)

Czyzowicz et al. 2012b

Results, in order of publication

Czyzowicz et al. 2012b current best

Memory \(O(\log n)\)

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

Pelc & Yadav 2019b current best

Time \((n+\tau)^{O(n+\tau)}\)

every feasible start: nonsymmetric nodes with any delay, or symmetric nodes \(u, v\) with delay \(\tau \ge \mathrm{Shrink}(u,v)\)no knowledge of \(n\), \(\tau\) or the start nodes

Introductory and current best for starts with a delay. Corollary 3.1: a start is feasible if and only if the nodes are nonsymmetric or \(\tau \ge \mathrm{Shrink}(u,v)\), the smallest distance at which the same sequence of ports leads from \(u\) and from \(v\) (Lemma 3.1 proves necessity); Algorithm UniversalRV meets for every feasible start (Theorem 3.1). The time bound is derived in Section 4.

Open questions

Is there a universal algorithm that meets for every feasible start in time polynomial in \(n\) and \(\tau\)? Posed in Pelc & Yadav 2019b.

Notes

With simultaneous start, rendezvous is feasible exactly when the two start nodes have different views. With a delay, symmetric start nodes become feasible once the delay reaches \(\mathrm{Shrink}(u,v)\) Pelc & Yadav 2019b; Pelc and Yadav credit Czyzowicz et al. 2012b with the nonsymmetric case, for agents that know an upper bound on \(n\) (as reported). Checked against the full text of Pelc & Yadav 2019b (arXiv v1).

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.