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 measurescollapse

Rendezvous of two labelled agents in a tree, simultaneous start, by the explore-or-wait idea of Dessmark et al. 2006 (simplified): after one depth-first tour to learn \(n\), each agent reads its label in binary with every bit doubled and \(01\) appended, and spends one block of \(2(n-1)\) rounds per bit, exploring and returning on a 1, waiting at its start node on a 0. Labels 1 and 3 give \(11\,01\) and \(11\,11\,01\); in block 3 agent 3 explores while agent 1 waits, and they meet. One frame per round.

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.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Two friends lose each other in a city with no phones and want to meet at the same spot. The city is a graph: street corners are nodes and the streets between them are edges; the friends are two agents that start at different nodes of this unknown connected graph. At each node the edges at that node carry local numbers, its ports. Time passes in synchronous rounds; in each round an agent stays or makes a move along one edge, and the agents meet when they are on the same node in the same round (crossing inside an edge does not count). In the basic version each agent knows its own label, a distinct integer from \(\{1,\dots,L\}\), but not the other's label and nothing about the graph; \(\lambda\) is the smaller of the two labels, \(n\) the number of nodes, and the later agent may start \(\tau\) rounds after the earlier one (the delay). The task is to meet, and the cost is the number of rounds from the start of the later agent.

1AlgorithmExplore or wait, bit by bit (trees, simultaneous start) Labelled agents in trees → Dessmark et al. 2006

If one agent knew it should wait, the other could simply search the graph ("wait for mommy" in Dessmark et al. 2006). Without knowing the other label, use the bits of your own label to take turns. This is a simplified version of their idea, for a tree (no cycles), both agents starting in the same round.

Explore the tree by depth-first search and return to your start node (the node where you began); you learn \(n\), and this takes \(2(n-1)\) rounds. Call \(2(n-1)\) rounds a block.
Write your label in binary, write every bit twice, and append \(0\,1\). For example \(5 = 101\) becomes \(11\,00\,11\,01\).
Go through this string one bit per block: on a bit 1, explore the tree and return to your start node; on a bit 0, wait at your start node for the whole block.

Why it works and what it costs. Both agents compute the same block length, so their blocks start and end in the same rounds. Two different labels give strings that differ at some position before the shorter one ends (the final \(0\,1\) marks the end, and no doubled bit looks like it). In that block one agent explores while the other waits at its start node, so the exploring agent walks onto it. The cost is \(O(\log\lambda)\) blocks of \(O(n)\) rounds, \(O(n\log\lambda)\) in all. Dessmark et al. 2006 reach \(O(n+\log\lambda)\) on trees even with a delay \(\tau\), which is optimal; on general graphs the best known is \(\tilde O(n^5\log\lambda)\) Ta-Shma & Zwick 2014, against a lower bound of \(\Omega(n^2)\).

Why it matters. Turning distinct labels into different move/wait patterns is the basic symmetry-breaking device of deterministic rendezvous.

2ImpossibilityIdentical agents in symmetric positions Anonymous agents: memory → Czyzowicz et al. 2012

Take a ring of 6 nodes where at every node port 0 leads clockwise and port 1 counterclockwise. Put two agents without labels (anonymous: same algorithm, same initial memory) on opposite nodes, 3 edges apart, starting in the same round. Each agent sees exactly what the other sees: a node of degree 2 (two edges at it), the same entry ports, nobody else around. So in every round they make the same choice: both stay, both go clockwise, or both go counterclockwise.

Why it holds. After any number of rounds they are still exactly 3 edges apart, so they never meet, whatever the algorithm and however much memory (bits kept between rounds) they have. Identical agents can meet only when their starting positions are not symmetric in this sense, and for those positions \(\Theta(\log n)\) bits of memory are exactly what is needed Czyzowicz et al. 2012.

Why it matters. It explains why most rendezvous work gives the agents labels, and why for identical agents the question becomes which starting positions can be told apart.

3Lower boundTwo nodes and the length of a label Labelled agents, arbitrary finite graphs → Dessmark et al. 2006

Take the smallest graph: two nodes joined by one edge, one agent at each end, both starting together. Until they meet, an agent sees nothing new (always degree 1, always port 0), so its behaviour in the first \(t\) rounds is a string of \(t\) choices, stay or move, fixed by its label alone. They meet in a round where exactly one of them moves; if both move they just swap ends.

Why it holds. There are only \(2^t\) strings of \(t\) choices. Among \(2^t + 1\) labels, two give the same string; give these labels to the two agents and they do the same thing in each of the first \(t\) rounds, so they do not meet within \(t\) rounds. Hence some pairs of labels need about \(\log\) (number of labels) rounds, which gives the \(\Omega(\log\lambda)\) bound of Dessmark et al. 2006. Together with the \(\Omega(n)\) needed to cover the graph it shows their \(O(n+\log\lambda)\) algorithm for trees is optimal.

Why it matters. It shows that the cost of breaking symmetry is the length of a label, a counting argument that recurs in every model with identifiers.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Memory

Asynchronous anonymous agents

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

unknown \(\text{finite}\) vs —

unknown — vs —

Asynchronous labelled agents

An adversary controls speeds; agents may meet inside an edge. Feasible everywhere, and at polynomial cost, but with very large exponents.

unknown \(\text{poly}(n,\log \lambda)\) vs —

unknown — vs —

Labelled agents, arbitrary finite graphs standard

Polynomial in \(n\) and \(\log \lambda\) and independent of the delay, but far from the known lower bounds.

polynomial gap \(\tilde O(n^5\log \lambda)\) vs \(\Omega(n^2)\) exploration

unknown — vs —

Labelled agents in trees

In trees, \(O(n+\log \lambda)\) even with arbitrary delay, and this cannot be improved.

tight \(O(n+\log \lambda)\) vs \(\Omega(n+\log \lambda)\) distance

unknown — vs —

Labelled agents in rings, simultaneous start

With simultaneous start on a ring, rendezvous takes \(\Theta(d\log \lambda)\) for initial distance \(d\).

tight \(O(d\log \lambda)\) vs \(\Omega(d\log \lambda)\) symmetry breaking

unknown — vs —

Anonymous agents: memory

Identical agents can meet whenever their positions are not symmetric, and \(\Theta(\log n)\) bits are exactly what it takes.

unknown — vs —

tight \(O(\log n)\) vs \(\Omega(\log n)\) symmetry breaking

Anonymous agents in trees, simultaneous start

With simultaneous start, memory drops to \(\Theta(\log \nu+\log\log n)\) for trees with \(\nu\) leaves; with delay it is \(\Theta(\log n)\), an exponential gap.

unknown — vs —

tight \(O(\log \nu+\log\log n)\) vs \(\Omega(\log \nu+\log\log n)\) symmetry breaking

Labelled agents, graphs with infinite degrees

A universal algorithm works even when nodes have infinite degree; it is within a cubic factor of the lower bound.

polynomial gap \(O((W\log L)^3)\) vs \(\Omega(\max(W,\log L))\) port addressing

unknown — vs —

Open questions 3

Asynchronous labelled agents

Find an optimal-cost asynchronous rendezvous algorithm in arbitrary graphs (open problem of Pelc 2019).

Labelled agents, arbitrary finite graphs

Find an optimal-time synchronous rendezvous algorithm for labelled agents in arbitrary graphs (open problem of Pelc 2019).

Labelled agents, graphs with infinite degrees

Find an optimal rendezvous algorithm, "even for finite graphs" Pattanayak & Pelc 2024.

What the community started looking at

Deterministic rendezvous in graphs started with the question of feasibility and cost polynomial in the graph size and the label length, for labelled agents that may start at different times Dessmark et al. 2006. The community then removed the dependence on the delay Kowalski & Malinowski 2008, made the algorithms constructive Ta-Shma & Zwick 2014, asked how little memory anonymous agents need Czyzowicz et al. 2012 Fraigniaud & Pelc 2013, and moved to asynchronous agents, where even feasibility in every graph took years De Marco et al. 2006 Czyzowicz et al. 2012 Dieudonné et al. 2015. Pelc's survey records this evolution Pelc 2019.

Subproblem of Graph exploration by a single agent

If the agents can break symmetry (for example by their labels), one may wait while the other explores, so exploration solves rendezvous; the work is in doing better than that, or in meeting when neither knows who should wait Pelc 2019.

Derived problems

Gathering in graphs: Rendezvous is gathering of two agents; with more agents the questions become which teams can gather, and how many faulty agents a team tolerates.

Perspectives

Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
Symmetry is the adversary Identical agents running the same deterministic program can be kept in lockstep forever. Across graphs, the plane and programmable matter, the papers break this symmetry with identifiers, with randomness, with asymmetric starts, or with the scheduler, and leader election keeps reappearing as the common core.
Finding your way A single agent in an anonymous graph: how much memory it needs, what a pebble, an advice string or knowledge of n buys, why stopping is harder than exploring, and how treasure hunt asks for exploration only as far as the target. Each line of papers, in its own words, on why the question matters.
Meeting at one place Rendezvous and gathering on graphs, gathering and convergence in the plane, and evacuation through an unknown exit all ask entities to end at one point. The papers give the same reasons for meeting, but each model makes a different part of it hard: symmetry and exploration on graphs, capability in the plane, information in continuous search.
What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.
The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

All settings

The assumption tree (8 settings, 2 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Memory); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Graph size › Identifiers › Timing › Start › Topology.

tight near-optimal polynomial gap unknown impossible no variant

No assumptions · 1 branches by graph dynamics Nothing is assumed on any axis.
- +static graph+undirected
  Graph size · 2 branches
  - +finite graph
    Asynchronous anonymous agents Which pairs of starting nodes allow identical asynchronous agents to meet is characterised.
    - +distinct IDs (eponymous)
      Asynchronous labelled agents An adversary controls speeds; agents may meet inside an edge. Feasible everywhere, and at polynomial cost, but with very large exponents.
      - +synchronous
        Labelled agents, arbitrary finite graphs standard setting draft Polynomial in \(n\) and \(\log \lambda\) and independent of the delay, but far from the known lower bounds.
        
        any delay+tree
        Labelled agents in trees In trees, \(O(n+\log \lambda)\) even with arbitrary delay, and this cannot be improved.
        
        +simultaneous start+ring
        Labelled agents in rings, simultaneous start With simultaneous start on a ring, rendezvous takes \(\Theta(d\log \lambda)\) for initial distance \(d\).
    - anonymous+synchronous
      Anonymous agents: memory Identical agents can meet whenever their positions are not symmetric, and \(\Theta(\log n)\) bits are exactly what it takes.
      - +simultaneous start+tree
        Anonymous agents in trees, simultaneous start With simultaneous start, memory drops to \(\Theta(\log \nu+\log\log n)\) for trees with \(\nu\) leaves; with delay it is \(\Theta(\log n)\), an exponential gap.
  - infinite degrees allowed+distinct IDs (eponymous)+synchronous
    Labelled agents, graphs with infinite degrees A universal algorithm works even when nodes have infinite degree; it is within a cubic factor of the lower bound.

Assumptions specific to this problem

Graph size

0finite or countably infinite, degrees may be infinite1finite or countably infinite, every degree finite2finite

Deterministic rendezvous in graphs was posed for finite graphs, where an agent can afford to explore the whole graph and the cost is a function of \(n\) Dessmark et al. 2006 Pelc 2019. Bhagat and Pelc argued that this approach "is inefficient for very large graphs, and cannot be used for infinite graphs", and gave the first synchronous algorithm for connected graphs with finite degrees and finitely or countably many nodes, with time polynomial in \(d\), \(\log L\) and the number of paths of length \(d\) from the starting nodes, a quantity that also bounds rendezvous from below in trees Bhagat & Pelc 2022. For asynchronous agents, Czyzowicz, Labourel and Pelc had already shown that rendezvous is feasible in every connected countable graph Czyzowicz et al. 2012 (as summarised in Pelc 2019); like all earlier work it assumed finite degrees Pattanayak & Pelc 2024. Pattanayak and Pelc then allowed countably infinite degrees, where the path count is infinite, and obtained a universal synchronous algorithm with time polynomial in a weight of the path types between the starting nodes and in \(\log L\), matched up to a polynomial by a lower bound in the tree whose degrees are all infinite Pattanayak & Pelc 2024. The axis thus separates three cost measures: \(n\), the local path count, and path-type weights.

Formal definitions

0infinite degrees allowed: \(G\) is finite or countably infinite; degrees may be infinite.
1locally finite: \(G\) is finite or countably infinite with finite degrees.
2finite graph: \(G\) has finitely many nodes.

Start

0arbitrary delay between the two starts1simultaneous start

Dessmark, Fraigniaud, Kowalski and Pelc treated two startup scenarios for deterministic rendezvous: simultaneous startup, and an arbitrary delay \(\tau\) chosen by the adversary, in which each agent counts rounds from its own wake-up without knowing \(\tau\) Dessmark et al. 2006. The delay is the stronger adversary: it can delay one agent long enough that the other must find it while it sleeps, which is treasure hunt Pelc 2019 Ta-Shma & Zwick 2014. It changes cost: on a ring simultaneous start gives \(\Theta(d\log \lambda)\), while with arbitrary delay \(\Omega(n+d\log \lambda)\) is a lower bound even when \(n\) is known; and the first polynomial algorithm for arbitrary graphs had cost growing with \(\sqrt\tau\), leaving open whether the dependence could be removed Dessmark et al. 2006, which Kowalski and Malinowski and then Ta-Shma and Zwick did Kowalski & Malinowski 2008 Ta-Shma & Zwick 2014 (the first as summarised in Pelc 2019). It also changes memory: Fraigniaud and Pelc showed that identical agents need \(\Theta(\log n)\) bits in trees with arbitrary delay, even on a line, but only \(O(\log\nu+\log\log n)\) bits with simultaneous start in trees with \(\nu\) leaves, an exponential gap when \(\nu\) is small Fraigniaud & Pelc 2013.

Formal definitions

0any delay: An adversary wakes the agents at times \(t_1\) and \(t_2\); the delay \(\tau=|t_1-t_2|\) is unknown.
1simultaneous start: Both agents start in the same round (\(\tau=0\)).

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.