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.
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Team
unknown
\(\text{poly}(n)\) vs \(\text{impossible}\)
symmetry
unknown
— vs —
unknown
\(O(n^3)\) vs —
unknown
— vs —
unknown
\(\text{poly}(n,\log\lambda)\) vs —
unknown
— vs —
Weakly Byzantine agents + at most weak Byzantine faults, + distinct IDs (eponymous), + synchronous
0 open · 1 results
unknown
\(\text{poly}(n,\log L)\) vs —
tight
\(f+2\) vs \(f+2\)
indistinguishable Byzantine agents
unknown
\(\text{poly}(n,\log\lambda)\) vs —
tight
\(f+1\) vs \(f+1\)
indistinguishable Byzantine agents
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.