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 graph, any topology
standard settingverifiedOn a 1-interval connected graph, \(n - 1\) agents always suffice, and the complete graph needs them all; the least number for a given graph is not characterised.
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: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- the complete graph \(K_n\)
- with at most \(n - 2\) agents (their \(n - 3\) ignorant agents) two nodes stay empty, and the adversary keeps open a spanning tree in which every ignorant agent is at least three edges from every source agent (Lemma 6.1)
- a 3-vertex-connected graph
- in every round the adversary connects the source agent's node to the rest only through a path of two empty nodes \(u\), \(r\) and a spanning tree of the graph without \(u\) and the source agent's node, so every ignorant agent is at least three edges away
- \(B\) a bond of pairwise disjoint edges (a minimal cut that is a matching)
- ignorant agents on one side, the source agent on the other; the adversary removes every edge of \(B\) with an agent at an endpoint
- the adversary places a source agent and an ignorant agent at distance \(D\)
- holds whenever the agents win
Results, in order of publication
Observation 3.4: with at most one empty node some source agent and ignorant agent are within two edges in every snapshot, so one meeting happens per round. Introductory and current best in the worst case.
Open questions
Which graph property determines the least number of agents that solve broadcast on a graph \(G\)? Edge density, edge connectivity and the number of redundant edges do not Moses Jr. et al. 2025; is there an analogue of dismantlability, which characterises cop-win graphs? Moses Jr. et al. 2026
How many rounds do the agents need when they win, as a function of \(n\) and \(D\)? Only lower bounds of order \(D\) are known Moses Jr. et al. 2026.
Can broadcast be solved with weaker agents than global visibility, for example agents that see only the source agent? Das et al. 2026b
Notes
On a tree the adversary can remove no edge, so two agents suffice (Observation 3.2 of Das et al. 2026b) and the time is \(\Theta(D)\) as on a static graph; a tree of diameter \(D\) forces \(\lceil D/2\rceil\) rounds with two agents (Theorem 23 of Moses Jr. et al. 2026). On cactus graphs (every edge on at most one cycle) the least number of ignorant agents is the number of cycles shorter than 5 if there are no others, and otherwise the number of cycles plus one (Theorem 4.2 of Das et al. 2026b). An upper bound for a graph is also an upper bound for each of its connected spanning subgraphs (Observation 3.3 of Das et al. 2026b). Moses, Redlich and Stock show that no simple graph property decides the least number of agents Moses Jr. et al. 2025: graphs with edge density (edges per node) \(1 + O(1/\log^* n)\) that need \(\Theta(n/\log^* n)\) agents (Theorem 4, Corollary 6); for every number of agents and every density above 1, graphs below that density that need that many agents (Theorem 7); graphs with large edge connectivity, or with constant edge density and edge connectivity, that need a linear number of agents (Theorem 8, Corollaries 9–10); generalized theta graphs (two nodes joined by internally disjoint paths) need exactly one agent per path plus the source agent when every path has length at least 3 in their terms (Theorems 2–3). In Moses Jr. et al. 2026 the winner is preserved by several constructions: adding edges cannot help the agents (Lemma 6); gluing a graph won by the adversary onto any graph at a cut node keeps it won by the adversary (Theorems 9–10); contracting cut edges does not change the winner (Theorem 14). If every set of \(k\) nodes has a spanning tree whose one-step moves can always be mapped onto an isomorphic spanning tree ("\(k\)-spanning tree symmetry"), the adversary wins with \(k\) agents even when the agents choose their start (Theorem 19). Das et al. and Moses Jr. et al. 2025 count ignorant agents with \(k\) (their \(k\) is \(k - 1\) here); Moses Jr. et al. 2026 counts all agents, as here.
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
Branches from here
Dynamic rings
Dynamic complete graphs
Dynamic bipartite graphs
Dynamic hypercubes
Dynamic grids
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.