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.
Homonymous agents
verifiedWhen agents may share labels, the teams that can always gather are fully characterised, and gather in time polynomial in \(n\) and \(\log\lambda\).
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: homonymous
- Each agent \(a\) has a label \(\mathrm{id}(a)\in\mathcal L\) known to itself (and revealed on meeting), but the labelling need not be injective: \(1\le|\{\mathrm{id}(a)\}|\le k\). With \(|\mathcal L|\) distinct labels, \(|\mathcal L|=1\) is the anonymous case and \(|\mathcal L|=k\) the eponymous one Delporte-Gallet et al. 2013.
- 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
Results, in order of publication
Introductory and current best; \(\lambda\) is the smallest label, \(L\) the largest.
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
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.