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.
Labelled agents in infinite trees
verifiedIn infinite regular trees the time grows with the number of nodes within distance \(d\): \(O(\mathrm{ball}(d)\log L)\) against \(\Omega(\mathrm{ball}(d)+d\log L)\).
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: locally finite
- \(G\) is finite or countably infinite with finite degrees.
- 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: 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: tree
- \(G\) is connected and acyclic: \(|E|=n-1\).
What is known
- regular trees of degree \(\Delta \ge 2\) with an adversarial port numbering, even with simultaneous start and known \(d\) and \(L\) (Theorem 2.2 and Corollary 2.3)
- \(\mathrm{ball}(d)\) is the number of nodes within distance \(d\) of a node, exponential in \(d\) when \(\Delta > 2\)
- with arbitrary delay \(\Omega(\mathrm{ball}(d))\) holds even in oriented trees, where a root is marked and port 0 leads towards it (Proposition 3.1)
Results, in order of publication
Introductory and current best (Theorem 2.1, Algorithm URT): each agent explores balls of growing radius, at times set by its transformed label. Time is counted from the wake-up of the earlier agent.
Open questions
Close the gap between \(O(\mathrm{ball}(d)\log L)\) and \(\Omega(\mathrm{ball}(d)+d\log L)\) in unoriented regular trees. Posed in Bhagat & Pelc 2024.
Find efficient rendezvous algorithms for arbitrary infinite graphs without extra knowledge such as the agents' positions. Posed in Bhagat & Pelc 2024.
Notes
Bhagat and Pelc express the time in the initial distance \(d\) instead of \(n\), since the tree may be infinite; their algorithms work in finite trees as well. Exploring a ball takes time linear in its size in a tree, but no such exploration is known in anonymous graphs with cycles, which is why they restrict to trees. Checked against the full text (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.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.