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
verifiedSeveral identical asynchronous agents with whiteboards build a common labelled map in \(O(m\log k)\) moves when \(n\) and \(k\) are co-prime; otherwise some placements are unsolvable.
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.
- 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.
Statement for this variant
\(k\) identical asynchronous agents start on \(k\) distinct nodes (their homebases, which are marked) of an anonymous graph with \(n\) nodes, \(m\) edges and arbitrary ports. Every node has a whiteboard that agents read and write in fair mutual exclusion; agents at the same node can talk. Each agent knows \(n\) or \(k\). Every agent must return to its homebase with the same labelled map: a copy of the graph with ports in which every node carries the same label in every agent's map. Cost is the total number of moves.
What is known
- \(\gcd(n,k) > 1\): on a symmetric graph such as a ring the agents can be placed symmetrically, so that no deterministic algorithm elects a leader (Lemma 2.2, derived from earlier results on election and rendezvous)
- map construction, leader election, labelling the nodes and rendezvous are solvable on exactly the same instances (Theorem 2.1)
- agents that know neither \(n\) nor \(k\) cannot solve every solvable instance (Lemma 2.1)
- some instances with \(\gcd(n,k) > 1\) are solvable, e.g. a tree with an odd number of nodes
Results, in order of publication
Algorithm MERGE-TREE (Theorems 5.1 to 5.3): solves the problem whenever \(\gcd(n,k) = 1\), and every agent terminates explicitly, also on instances it cannot solve.
Algorithm Explore-&-Capture (Theorems 6.1 and 6.2): at most \(\log k\) phases of \(O(m)\) moves each.
Open questions
None recorded for this variant.
Notes
Checked against the full text of Das et al. 2007. Both algorithms first let every agent explore and mark a territory around its homebase with a depth-first search (\(4m - 2n + 2k\) moves in total, Lemma 3.2), then merge territories in phases: neighbouring territories compare tokens (number of nodes and number of agents), and the smaller is captured. If all territories have the same counts, \(\gcd(n,k) > 1\), which is how the agents detect an instance the algorithm cannot solve (Lemmas 5.3 and 5.4). Each agent stores a full map in its own memory; the whiteboards need only \(O(\log n)\) bits (Theorem 6.2).
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.