Broadcast by agents in dynamic graphs
One agent holds a message; an adversary changes the graph every round, keeping it connected. How many agents are needed so that the message always reaches every agent?
Problem statement and measuresexpand
\(k \ge 2\) agents with distinct identifiers stand on distinct nodes, chosen by an adversary, of a connected undirected graph \(G = (V, E)\) with \(n\) nodes. One agent, the source agent, holds a message; the other \(k - 1\) are ignorant agents. Time runs in synchronous rounds. At the start of every round the adversary chooses the snapshot \(G_t\), any connected spanning subgraph of \(G\) (the dynamic graph is 1-interval connected); every agent then sees \(G_t\) and the position and status of every agent (global visibility), and moves along one edge of \(G_t\) or stays. An ignorant agent that is on the same node as a source agent receives the message and becomes a source agent; no message travels in any other way. Broadcast is solved when every agent holds the message. The question is, for each graph \(G\), the least \(k\) with which the agents solve broadcast against every adversary and every initial placement; time is the number of rounds.
Measures: Agents, the least number \(k\) of agents, the source agent included, with which broadcast is solved against every adversary, in the worst case over the graphs of the setting with \(n\) nodes; Time, rounds until every agent holds the message.
Dynamic grids
verifiedOn a \(\sqrt n \times \sqrt n\) grid between \((\sqrt n - 1)^2 + 1\) and \(n - 3\) agents are needed; on a \(2 \times b\) grid, \(b\) or \(b + 1\).
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: connected every round
- \(\mathcal G=(G_t)_{t\ge0}\) is 1-interval connected if every snapshot \(G_t=(V,E_t)\) is connected. More generally it is \(T\)-interval connected if for every \(t\) the graph \(\bigl(V,\bigcap_{i=t}^{t+T-1}E_i\bigr)\) is connected.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- 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.
- Communication: local communication
- Agents at the same node at the same time can read each other's entire memory (face-to-face communication). Agents crossing on an edge do not meet.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Initial configuration: dispersed start
- Every initially occupied node holds exactly one agent (\(\ell=k\)). Also called a scattered start, notably in black hole search.
- Topology: grid
- \(G\) is a \(\sqrt n\times\sqrt n\) grid graph; whether ports are globally consistent (oriented) is stated per result.
What is known
- an \(a \times b\) grid with \(a, b \ge 2\) needs \((a - 1)(b - 1) + 1\) agents; the square grid is the case \(a = b = \sqrt n\)
- the adversary puts the source agent in the two bottom rows with too few ignorant agents, \(b - 1\) ignorant agents on every other row, and opens an edge between the two parts only at an empty node (Lemmas 5.4–5.5)
Results, in order of publication
Grids are bipartite, so the bipartite bound applies (Lemma 6.2 with Observation 3.3); on a \(2 \times b\) grid \(b + 1\) agents suffice (Theorem 5.2). Introductory and current best.
Open questions
Close the gap between \((\sqrt n - 1)^2 + 1\) and \(n - 3\) agents on the \(\sqrt n \times \sqrt n\) grid Das et al. 2026b.
Notes
The grid of this setting is the model's square grid; the bounds hold for every \(a \times b\) grid with \(a, b \ge 2\) (\(a\) rows, \(b\) columns).
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
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.