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

Asynchronous anonymous agents

verified

Time: unknownMemory: unknown

Which pairs of starting nodes allow identical asynchronous agents to meet is characterised.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Graph sizefinite

Not assumed

Identifiersanonymous: all agents are identicalTimingasynchronousStartarbitrary 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: asynchronous: Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
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

Cost not studied.

lower boundnone known

introductory—

current best

\(\text{finite}\)

Guilbault & Pelc 2011

Memory · bits per agent

unknown

Memory is unbounded.

lower boundnone known

introductory—

current best—

Results, in order of publication

Guilbault & Pelc 2011 current best

Time \(\text{finite}\)

Introductory and current best. Feasible iff the views differ or the two nodes are joined by a path whose port sequence is a palindrome (as summarised in Pelc 2019); randomized agents meet with probability 1.

Open questions

None recorded for this variant.

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.