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.
Anonymous agents on paths and rings with labelled nodes
verifiedOn paths with labelled nodes, two anonymous agents meet in \(O(d\log^*\sigma_{\min})\) rounds, \(\sigma_{\min}\) the smallest node label near their start nodes, and no algorithm is faster in the worst case.
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: labelled nodes
- Each node \(v\) carries a distinct identifier that agents at \(v\) can read; hence an agent can recognise a node it has visited.
- 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: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
Statement for this variant
The graph is a path or a ring, finite or infinite: in the main case the two-way infinite path, every node of degree 2. Every node \(v\) carries a distinct node label \(\sigma(v)\in\{1,2,\dots\}\) that an agent reads when it is at \(v\). The two agents are anonymous: they run the same deterministic algorithm and can break symmetry only through the node labels they see. An adversary wakes them at times of its choice; an awake agent that reaches the node of a sleeping agent meets it. They know neither \(d\) (the distance between their start nodes) nor the delay \(\tau\), share no orientation, see the port by which they enter a node, and do not notice crossing inside an edge. \(\sigma_{\max}\) is the larger node label of the two start nodes, and \(\sigma_{\min}\) the smallest node label within distance \(O(d)\) of the start nodes; \(\log^*\) is the iterated logarithm, taken to be at least 1.
What is known
- an algorithm that always meets within \(\frac{1}{16\kappa}\log^*\sigma_{\max}\) rounds from adjacent start nodes would give a 3-colouring algorithm for labelled paths in the LOCAL model faster than Linial's lower bound allows (\(\kappa\) the constant of their colouring algorithm; Theorem 4.9); for \(d > 1\), \(d - 1\) nodes inserted between consecutive nodes reduce to \(d = 1\) (Theorem 4.10)
- a two-way infinite path made of consecutive segments, each labelled so that 3-colouring it needs time close to Linial's bound
- holds even with simultaneous start, known \(d\) and a global sense of direction
Results, in order of publication
Theorem 5.31 of the arXiv version: each agent knows only the node label of its start node. The algorithms 3-colour the path around the start nodes with an early-stopping version of the Cole–Vishkin algorithm, so that a node with a small node label stops early (Theorem 2.1), and let the colours decide which agent waits while the other searches. On finite paths and rings with \(n\) nodes, \(O(\min(n, d^2(\log^*\sigma_{\max})^3))\).
Theorem 1.1 (arXiv v2), on the two-way infinite path, counting rounds from the wake-up of the earlier agent; Corollary 1.2 gives \(O(\min(n, d\log^*\sigma_{\min}))\) on finite paths and rings with \(n\) nodes, and Remark 5.1 a faster bound when a start node is near an end of a finite path. Since \(\sigma_{\min}\le\sigma_{\max}\) it is never slower than \(O(d\log^*\sigma_{\max})\). It improves the \(O(d^2(\log^*\sigma_{\max})^3)\) algorithm of Miller & Pelc 2025 for unknown \(d\), and needs no knowledge of \(d\) to match their \(O(d\log^*\sigma_{\max})\) algorithm for known \(d\).
Theorem 4.2: optimal when \(d\) is known. If each agent also knows its position relative to the node with the smallest node label, \(O(d)\) rounds suffice for any delay (Theorem 3.4).
Open questions
None recorded for this variant.
Notes
Bourreau, Narayanan and Nolin let each agent explore a growing interval around its start node and compute from the node labels it has seen a sparse set of nodes, a ruling set of the path with spacing \(\Theta(d)\), coloured with 17 colours so that nearby members get different colours (Lemma 3.5). Each agent walks to the nearest member and alternates searching and waiting according to the bits of its colour, so that one agent searches while the other waits (Algorithm 5, Lemmas 4.3 to 4.7). The computation is an early-stopping version of distributed colouring in the LOCAL model, in which a node with a small node label decides early; this is why the bound depends on \(\sigma_{\min}\). Procedure CarefulWalk crosses an edge in 4 rounds, with moves that depend on whether the node label increases across the edge, so that two agents can no longer swap places inside an edge without meeting (Theorem 3.1). Without node labels, labelled agents on a ring with simultaneous start need \(\Theta(d\log\lambda)\) rounds Dessmark et al. 2006; Bourreau et al. draw this contrast in their Table 1. Miller and Pelc left open the optimal time when \(d\) is unknown Miller & Pelc 2025; Bourreau, Narayanan and Nolin settled it. Miller and Pelc also separate three ways of learning the node labels when \(d\) is known: \(\Theta(d)\) if the whole labelling is known in advance, \(\Theta(d\log^*\sigma_{\max})\) if node labels are seen on visits, and \(\Theta(d\log\sigma_{\max})\) if only the start node's label is seen, which is the case of labelled agents in an anonymous graph. Bourreau et al. 2026 read in arXiv v2 (January 2026) and Miller & Pelc 2025 in arXiv v1 (2023); theorem numbers refer to these versions. Both bounds were checked against the full texts.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.