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.
Static graph
verifiedWithout edge changes two agents suffice on every graph and broadcast takes \(\Theta(D)\) rounds.
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.
- 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 adversary places the source agent and an ignorant agent at distance \(D\)
- two agents close their distance by at most two per round
Results, in order of publication
Observation 3.1: every agent walks towards the source agent. Introductory and current best.
Open questions
None recorded for this variant.
Notes
Global visibility makes the static case a shortest-path walk; the case is listed as the base against which the adversary's power is measured.
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.