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.
Anonymous agents
standard settingverifiedWhich configurations of identical agents can gather is characterised; detecting that gathering is complete needs a bound on \(n\).
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.
- Faults: no faults
- All agents follow the algorithm forever.
- 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.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- gathering with detection by a universal algorithm when no bound on \(n\) is known
Results, in order of publication
Introductory and current best; without a bound, gathering without detection in time polynomial in the actual size.
Open questions
None recorded for this variant.
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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.