Mobility Matters
Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent›Rendezvous›Gathering in graphs

Gathering in graphs

Several agents must all meet at one node of an unknown graph, possibly despite faulty agents.

Problem statement and measurescollapse
123112114: 11 00 00 013: 11 11 012: 11 00 012223344Start: agents 2, 3, 4 at distinct nodes of a treeBlock 0: every leader explores (learns n; block = 8 rounds)Leaders 2 and 4 meet: 2 now follows 4Block 1: leader 3 explores, leader 4 exploresBlock 2: leader 3 explores, leader 4 exploresFinal: leader 3 walks onto the waiting group of 4 (round 25)
Gathering of labelled agents by merging rendezvous Dessmark et al. 2006: each leader runs the explore-or-wait rendezvous of a tree with its own label (after one tour to learn \(n\), one block of \(2(n-1)\) rounds per bit of its doubled label followed by \(01\): explore on 1, wait at its start node on 0); when groups meet, the largest label stays leader and the others follow it. Colours show the leader each agent follows; one frame per round. Gathering is reached, but without detection.

\(k \ge 2\) agents start at different nodes of an unknown connected graph and must all be at the same node at the same time, and (with detection) know it. Time is in rounds; team is the number of good agents needed when some agents are Byzantine (faulty agents that move arbitrarily and may lie).

Measures: Time, rounds until all agents meet; Team, good agents needed when \(f\) agents are Byzantine.

A first look

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

A group of hikers scattered over a trail network wants to get together at one spot, with no phones and no map. The network is a graph: trail junctions are nodes and the trails between them are edges; the hikers are \(k \ge 2\) 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, and in each round an agent stays or moves along one edge. All agents must be at the same node at the same time and, in the version with detection, know that everyone has arrived. In the basic version the agents are anonymous (identical: same algorithm, no labels, that is, no distinct integers that tell them apart), there are no faults, and \(n\) denotes the number of nodes; the question is which starting configurations (the sets of nodes on which the agents start) can be gathered, and how fast.

1AlgorithmMeet in pairs, then follow the largest label Labelled agents →

A standard approach for agents with distinct labels that can read each other's label when they are at the same node. It uses any rendezvous algorithm for two labelled agents (an algorithm that makes two agents meet at one node) that works whatever the delay between their starts, such as the one of Dessmark et al. 2006.

  1. Every agent starts as the leader of a group containing only itself, and runs the rendezvous algorithm with its own label.
  2. When groups meet at a node, everyone there adopts the largest label present; the agent with that label remains a leader and continues its own rendezvous algorithm as if nothing had happened.
  3. Every other agent stops being a leader and from now on simply follows its leader's moves.
Why it works and what it costs. A leader's walk is exactly what it would do alone, so any two leaders are guaranteed to meet by the rendezvous algorithm, and at each such meeting one of them stops being a leader. The agent with the largest label is never absorbed, and every other leader meets its group at the latest when it meets that agent, so eventually all \(k\) agents move as one group. The time is at most \(k-1\) rendezvous times. This gives gathering but not detection: knowing that nobody is missing needs extra knowledge, for example of \(n\); with more than \(n/2\) agents and \(n\) known, Molla et al. 2023 gather with detection in \(O(n^3)\) rounds.

Why it matters. Reducing gathering to repeated rendezvous with merging is the simplest way to see why distinct labels make gathering solvable.

2ImpossibilitySymmetric configurations of identical agents Anonymous agents → Dieudonné & Pelc 2016

Take a ring of 6 nodes, with port 0 leading clockwise and port 1 counterclockwise at every node, and put three identical agents on every second node. Starting together, each agent sees exactly what the others see, so in every round all three make the same choice. Turning the ring by two nodes maps the configuration to itself before the round and after it.

Why it holds. So the agents always stay on three different nodes, two edges apart, and never gather, whatever the algorithm. For identical agents the question is therefore which configurations can be gathered at all; Dieudonné & Pelc 2016 characterise them and gather every such configuration in time polynomial in \(n\), but detecting that gathering is complete needs an upper bound on \(n\).

Why it matters. It shows that for identical agents the right question is which starting configurations are solvable, not only how fast.

3ImpossibilityByzantine agents can impersonate the whole team Byzantine agents → Dieudonné et al. 2014

Some agents may be Byzantine: faulty agents that move arbitrarily and, in the strong version, may lie about their labels. Take \(f = 2\) good agents, labelled 0 and 1, and 2 Byzantine ones, on a ring of 4 nodes \(v_0, v_1, v_2, v_3\) with port 0 leading clockwise everywhere. Run 1: good agents 0 and 1 on \(v_0, v_1\); the two Byzantine agents on \(v_2, v_3\) claim labels 0 and 1 and follow the algorithm honestly. The configuration is symmetric, so when the good agents gather at some node \(v_i\) and stop, the Byzantine agents stop at the opposite node \(v_{i+2}\). Run 2: the same, except good agent 0 and the Byzantine agent claiming label 0 swap starting nodes.

Why it holds. Every agent sees in run 2 exactly what it saw in run 1, so everyone does the same thing; at the end good agent 1 stands with the Byzantine agent claiming label 0 on one node and good agent 0 stands with the Byzantine agent claiming label 1 on the opposite node, and both groups stop. The good agents are not gathered, so with \(f\) strongly Byzantine agents, \(f\) good agents cannot gather, even if \(n\) is known Dieudonné et al. 2014 (their Theorem 4.7, for every \(f\), on a ring of \(2f\) nodes). With \(f+1\) good agents (\(n\) known) or \(f+2\) (\(n\) unknown) gathering becomes possible Bouchard et al. 2016.

Why it matters. This "two indistinguishable runs" argument is the standard way to prove that faulty agents make a task impossible, and it shows how many good agents a fault-tolerant algorithm must assume.

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
Team
Anonymous agents standard
Which configurations of identical agents can gather is characterised; detecting that gathering is complete needs a bound on \(n\).
unknown \(\text{poly}(n)\) vs \(\text{impossible}\) symmetry
unknown — vs —
Labelled agents
Labelled agents gather even without talking; with many agents gathering with detection takes \(O(n^3)\) rounds.
unknown \(O(n^3)\) vs —
unknown — vs —
Homonymous agents
When agents may share labels, the teams that can always gather are fully characterised, and gather in time polynomial in \(n\) and \(\log\lambda\).
unknown \(\text{poly}(n,\log\lambda)\) vs —
unknown — vs —
Weakly Byzantine agents
With \(f\) weakly Byzantine agents and \(f\) known, one good agent suffices when \(n\) is known and \(f+2\) are necessary and sufficient when it is not; when nothing is known, no team can gather.
unknown \(\text{poly}(n,\log L)\) vs —
tight \(f+2\) vs \(f+2\) indistinguishable Byzantine agents
Byzantine agents
With \(f\) strongly Byzantine agents, \(f+1\) good agents (known \(n\)) or \(f+2\) (unknown \(n\)) are necessary and sufficient.
unknown \(\text{poly}(n,\log\lambda)\) vs —
tight \(f+1\) vs \(f+1\) indistinguishable Byzantine agents

Open questions 3

Labelled agents

  1. Gathering without communication when no bound on \(n\) is known.

Weakly Byzantine agents

  1. Can weakly Byzantine agents solve self-stabilizing perpetual gathering (from arbitrary memory states, all good agents eventually always at one node) with no global knowledge? Hirose et al. 2025 solve it with upper bounds on \(n\), \(k\) and \(f\) and the length of the largest label of a good agent, and leave this open.

Byzantine agents

  1. Polynomial-time Byzantine gathering with teams of size close to \(f+1\).

What the community started looking at

Gathering of many agents in graphs was studied as the natural extension of rendezvous Pelc 2019: first which configurations can gather at all Dieudonné & Pelc 2016, then how many faulty agents a team can tolerate Dieudonné et al. 2014 Bouchard et al. 2016, and only then time Bouchard et al. 2022 Molla et al. 2023.

Generalisation of Rendezvous

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

Derived problems

Gathering by oblivious robots on graphs: The task is that of gathering in graphs, all entities on one node, but the entities are oblivious Look–Compute–Move robots, as in exploration by oblivious robots: they see the positions of all robots, remember nothing, carry no labels and send no messages. Whether a start can be gathered then depends on the symmetries of the configuration, on what a robot sees of robots sharing a node, and on the scheduler. Results do not transfer directly in either direction.

Related problems

Broadcast by agents in dynamic graphs: Every ignorant agent must meet a source agent, so any algorithm that gathers all agents on one node in a setting also solves broadcast there; broadcast asks only for the meetings that pass the message on.

Deciding graph properties by mobile agents: Gathering is what makes a known number of agents decisive: after it, the agents learn the whole configuration Fraigniaud & Pelc 2017.

Perspectives

  • 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.
  • 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.
  • When agents fail A node that destroys visitors, a robot that stops, an agent that lies, a searcher that misses the target: the papers motivate each fault by the hardware or the network, and each kind of fault changes a different measure, from team size to feasibility to an exact constant.
  • 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.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Gao & Pelc 2026 Gathering teams of bounded memory agents on a line. Labelled agents that are finite automata (their number of states depends only on \(L\)) start in the same round in teams, all agents of a team on one node, on an infinite path without node names, and must gather and stop: with teams of one agent the adversary can prevent every meeting even when the two ports of every edge differ (Theorem 3.1); with equal teams of at least two agents, gathering takes time linear in the largest distance between the starting nodes of two teams when the two ports of every edge differ (Theorem 4.1), and with arbitrary ports \(\Theta(\log L)\) times that distance for teams of two (Theorems 5.1, 5.2), linear time for larger teams (Theorem 5.3) and for teams of different sizes (Theorems 6.1, 6.2); the agents know \(L\) and the number of teams, which Section 7 argues is necessary, as is the simultaneous start. Read (arXiv v1).
  • Bärtschi et al. 2021 Near-gathering of energy-constrained mobile agents. Near-gathering of \(k\) agents with energy budgets in an edge-weighted graph, where gathering at one point may be impossible: minimising the radius of a ball containing all agents is polynomial; minimising the largest distance between two agents has a 2-approximation and a matching NP-hardness bound; minimising the average distance has a \(2(1-1/k)\)-approximation but no FPTAS unless P = NP. Abstract read.
  • Pelc 2018c Use of information, memory and randomization in asynchronous gathering. Gathering on a grid by copies of a state machine: with initial input, unbounded memory and randomization every configuration is gathered with probability 1, and no two of these suffice; deterministic machines gather all connected configurations. Abstract read.
  • Hirose et al. 2024 Fast gathering despite a linear number of weakly Byzantine agents†. Weakly Byzantine gathering in synchronous anonymous networks without whiteboards: \(O(f\,|\Lambda_{good}|\,X(N))\) rounds with \(N \ge n\) known, simultaneous start and \(k \ge 9f + 8\), by simulating Byzantine consensus; \(|\Lambda_{good}|\) is the length of the largest good identifier. Abstract and Table 1 read.
  • Tsuchida et al. 2018 Byzantine-Tolerant Gathering of Mobile Agents in Arbitrary Networks with Authenticated Whiteboards. Gathering of \(k\) agents with unique identifiers in asynchronous arbitrary graphs with authenticated whiteboards, despite \(f\) weakly Byzantine agents: two algorithms, with and without termination detection. Abstract read.
  • Miller & Saha 2020 Fast Byzantine Gathering with Visibility in Graphs. Gathering of \(m\) synchronous robots in a graph despite \(f\) Byzantine robots that may change their identifiers, when robots can see further than their own node. Abstract read.
  • Das et al. 2019b Gathering of robots in a ring with mobile faults. Gathering on a ring despite a fast malicious agent that blocks paths: for synchronous agents more cases are solvable on unoriented rings than for asynchronous ones. Abstract of the ICTCS 2016 version read.
  • Shibata et al. 2016 Partial gathering of mobile agents in asynchronous unidirectional rings. Partial gathering (\(g\) agents per meeting node suffice) in asynchronous unidirectional rings with whiteboards: three algorithms and their move complexity. Abstract read.
  • Shibata et al. 2019 Partial Gathering of Mobile Agents in Arbitrary Networks. Partial gathering in arbitrary graphs. Abstract read.
  • Bouchard 2019 On the Deterministic Gathering of Mobile Agents. A PhD thesis on deterministic gathering of mobile agents. Abstract read.
  • Di Luna et al. 2020c Gathering in dynamic rings. Gathering in dynamic rings in which one edge may be missing at each time: feasibility and complexity by chirality and cross detection. Abstract read.
  • Bournat et al. 2018 Gracefully Degrading Gathering in Dynamic Rings. Gracefully degrading gathering in dynamic rings: gather when the dynamics allow, and solve a weaker task when they do not. Abstract read.
  • Shibata et al. 2026 Partial gathering of mobile agents in dynamic rings. Partial gathering (\(g\) agents per meeting node) in synchronous dynamic bidirectional rings. Abstract read.
  • Das et al. 2021a Compacting oblivious agents on dynamic rings. Oblivious agents on dynamic rings must form a compact block. Abstract read.
  • Hirose et al. 2022 Weakly Byzantine Gathering with a Strong Team. Weakly Byzantine gathering of agents with unique identifiers in synchronous anonymous networks without whiteboards, with a large enough team of good agents ('strong team'), faster than the general algorithm. Abstract read.
  • Saxena & Mondal 2024 A further study on weak Byzantine gathering of mobile agents. Weakly Byzantine gathering of agents with unique labels in synchronous anonymous networks, with delayed starts, when the agents know \(n\) but not \(f\), \(k\) or the range of labels: \(f^2+4f+9\) good agents gather and stop in the same round within \(O(k^2\,X(n))\) rounds times the length of the largest label of a good agent (Theorem 4.1), where \(X(n)\) is the time to explore any \(n\)-node graph; Hirose et al. needed \(4f^2+8f+4\) good agents. Read in full (ICDCN version).
  • Shibata et al. 2020 Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings. Partial gathering (\(g\) agents or none on every node at the end, \(2 \le g \le k/2\)) in asynchronous unidirectional rings with whiteboards, by anonymous agents that know \(g\) but neither \(k\) nor \(n\): the unsolvable starts are those for agents that know \(k\), periodic configurations whose period is below \(g\), and no agent can detect them (Theorem 2); from every other start \(O(gn)\) moves in total (Theorem 3), which is optimal since \(\Omega(gn)\) are needed (Theorem 1, from Shibata et al. 2016); a randomized algorithm solves every start with probability 1 in \(O(gn)\) expected moves (Theorem 4). Read in full.
  • Das et al. 2019a Compacting and Grouping Mobile Agents on Dynamic Rings. Compacting instead of gathering on a 1-interval connected unoriented ring: synchronous Look–Compute–Move agents on distinct nodes must occupy consecutive nodes without ever sharing one, and with several colours each colour must form its own segment. Impossible from periodic starts even with global vision (Theorem 1), and with local vision even from asymmetric starts (Theorem 2). With global vision: from asymmetric starts within \(n\) rounds (Theorem 3), and from symmetric starts exactly when the axis does not pass through two empty nodes (Theorems 4, 5); the coloured version is treated in the same way, for two colours and for more (Sections 4 and 5). Read (model and theorems).

All settings

The assumption tree (5 settings, 3 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, Team); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Faults › Identifiers › Timing › Topology.

tight near-optimal polynomial gap unknown impossible no variant

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