Map construction
Agents must not only visit every node but output a map of the anonymous graph, up to isomorphism.
Problem statement and measuresexpand
Agents explore an unknown anonymous port-labelled graph and must output a map: a port-labelled graph, kept in the agent's memory, that is isomorphic to the explored graph (with the ports), with the agent's current node indicated. Time is the number of moves.
Measures: Cost, moves until the map is built.
Identical agents with whiteboards
draftCost: unknown
Several identical agents with whiteboards build a common labelled map exactly when symmetry can be broken.
Assumed (added on the last edge are outlined)
+Graph dynamicsstatic graph+Edge directionundirected+Agentsseveral identical agents+Whiteboardswhiteboards at the nodes
Not assumed
TimingasynchronousKnowledgenothing knownMarkersno markersTopologyarbitrary 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.
- Timing: asynchronous
- Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
- Agents: several agents
- \(k\ge2\) identical agents.
- Knowledge: nothing known
- Nothing is known about \(G\).
- Markers: no markers
- No markers.
- Whiteboards: whiteboards
- Each node has a whiteboard.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
Cost · moves until the map is built
unknown
Costs not checked.
lower bound
\(\text{impossible}\) Das et al. 2007
bottlenecksymmetry
holds when
- some configurations of identical agents
introductory—
Results, in order of publication
Das et al. 2007 current best
Cost \(\text{finite}\)
\(n\) and \(k\) co-prime
Introductory and current best.
Open questions
None recorded for this variant.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.