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.
Weakly Byzantine agents
verifiedWith \(f\) weakly Byzantine agents, one good agent suffices when \(n\) is known and \(f+2\) are necessary and sufficient when it is not.
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: at most weak Byzantine faults
- Up to \(f\) agents behave arbitrarily but always report their own true identifier.
- 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
- \(n\) unknown
- Theorem 3.11: \(f+1\) good agents cannot gather deterministically with termination in some networks
Results, in order of publication
Introductory and current best (Theorem 3.10, unknown \(n\)); time polynomial in \(n\) and in the length of the largest label of a good agent. With known \(n\), any number of good agents gather within \(4n^4\cdot P(n,\log L)\) rounds (Theorem 3.6; \(P\) is the polynomial time bound of the rendezvous algorithm of Ta-Shma and Zwick Ta-Shma & Zwick 2014).
Open questions
None recorded for this variant.
Notes
Checked against the full text of Dieudonné et al. 2014. Dieudonné, Pelc and Peleg note that \(f+2\) is a new threshold for tolerating \(f\) Byzantine entities, next to \(f+1\) for communication through a cut and \(2f+1\) processors for consensus in a complete network.
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.