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.
Asynchronous labelled agents
verifiedAn adversary controls speeds; agents may meet inside an edge. Feasible everywhere, and at polynomial cost, but with very large exponents.
Assumed (added on the last edge are outlined)
Not assumed
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: 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
Results, in order of publication
On a ring of known size, cost \(O(n\log \lambda)\), which is optimal.
Feasible in every connected countable graph without any knowledge; cost at least exponential.
Open questions
Find an optimal-cost asynchronous rendezvous algorithm in arbitrary graphs (open problem of Pelc 2019).
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.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Branches from here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.