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, one good agent suffices when \(n\) is known and \(f+2\) are necessary and sufficient when it is not.
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 2

Labelled agents

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

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.

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.

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.