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 measuresexpand

\(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.

no assumptions›+ static graph, + undirected›+ no faults›+ distinct IDs (eponymous), + synchronous

Labelled agents

verified
Time: unknownTeam: unknown

Labelled agents gather even without talking; with many agents gathering with detection takes \(O(n^3)\) rounds.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Faultsno faults+Identifiersdistinct identifiers (eponymous): agents have pairwise distinct identifiers+Timingsynchronous rounds

Not assumed

Topologyarbitrary connected graph
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.
Faults: no faults
All agents follow the algorithm forever.
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.
Topology: any topology
\(G\) is any connected graph in the class allowed by the other axes.

What is known

Time · rounds until all agents meet
unknown
No lower bound recorded.
lower boundnone known
introductory—
current best
\(O(n^3)\)
more than \(n/2\) agents\(n\) known
Team · good agents needed when \(f\) agents are Byzantine
unknown
—
lower boundnone known
introductory—
current best—

Results, in order of publication

Bouchard et al. 2023 also
Time \(\text{finite}\)

Gathering with no communication at all.

Molla et al. 2023 current best
Time \(O(n^3)\)
more than \(n/2\) agents\(n\) known

Gathering with detection.

Open questions

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

Notes

Two-agent gathering is rendezvous. For Look–Compute–Move robots on rings see Klasing et al. 2008.

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

Homonymous agents
Time \(\text{poly}(n,\log\lambda)\)
Weakly Byzantine agents
Time \(\text{poly}(n,\log L)\)Team \(f+2\)

Lower bounds from stronger settings hold here

No catalogued stronger setting.

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