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.
Byzantine agents
verifiedWith \(f\) strongly Byzantine agents, \(f+1\) good agents (known \(n\)) or \(f+2\) (unknown \(n\)) are necessary and sufficient.
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: any faults
- Up to \(f\) agents behave arbitrarily (adversarially) and may forge identifiers, i.e. report any label in \(\mathcal L\).
- 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
- Theorem 4.7: \(f\) good agents cannot gather deterministically against \(f\) strongly Byzantine agents
- holds even in a ring of known size
- \(n\) unknown
- inherited from weakly Byzantine agents (Theorem 3.11)
Results, in order of publication
Introductory (Theorems 4.5 and 4.6): \(2f+1\) good agents with known \(n\), \(4f+2\) with unknown \(n\); deterministic but exponential time. For known \(n\) and constant \(f\) a randomized algorithm gathers \(2f+1\) good agents in polynomial time with probability at least \(1-1/n\) (Theorem 4.4).
First polynomial-time Byzantine gathering. \(\lambda\) is the smallest label of a good agent (the paper's \(|l_{min}|\) is \(\log\lambda\) here).
Open questions
Polynomial-time Byzantine gathering with teams of size close to \(f+1\).
Notes
Checked against the full text of Dieudonné et al. 2014 for its bounds; the agents cannot mark nodes, agents at the same node exchange all information, the adversary may wake agents at different times, and good agents must gather and terminate simultaneously. The paper's results for known \(n\) also hold with a known polynomial upper bound on \(n\).
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.