Home›Mobile agents on graphs›Computing with agents›Minimum spanning tree by agents

Minimum spanning tree by agents

\(n\) agents in an anonymous weighted graph must build a minimum spanning tree.

Problem statement and measuresexpand

\(n\) agents with distinct identifiers (IDs) are placed on the nodes of an anonymous port-labelled graph with \(n\) nodes, \(m\) edges and maximum degree \(\Delta\). The start is rooted (all agents on one node), dispersed (one agent on each node) or arbitrary. Agents compute only by moving and by talking with agents on the same node. The agents must build a minimum spanning tree of the edge-weighted graph, each agent knowing which incident edges belong to it: every agent (or node) learns its part of the output. Time is in synchronous rounds; memory in bits per agent.

Measures: Time, rounds; Memory, bits per agent.

no assumptions›+ static graph, + undirected, + distinct IDs (eponymous), + local communication, + synchronous, + dispersed start

Dispersed start

standard settingverified

Time: unknownMemory: unknown

From a dispersed start, an MST takes \(O(n\log n+\Delta\log^2 n)\) rounds with \(O(\log n)\) bits.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Identifiersdistinct identifiers (eponymous): agents have pairwise distinct identifiers+Communicationlocal (co-located agents communicate)+Timingsynchronous rounds+Initial configurationdispersed or scattered (one agent per occupied node)

Not assumed

Knowledgeno knowledge of graph parametersTopologyarbitrary connected graph

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.
Knowledge: no knowledge: Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
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.