Brief Announcement: Optimal Dispersion Under Asynchrony

We now describe a modified DFS traversal, DFS_P1Tree(), that constructs a P1Tree. This algorithm forms the backbone of our agent-based dispersion strategy. Each node has two states: empty and occupied. We further categorize each node $v\in G$ into one of four types:

• $\mathrm{■}$

  unvisited: $v$ has not yet been visited by the DFS.

• $\mathrm{■}$

  fullyVisited: $v$ has been visited, and all its neighbors have also been visited.

• $\mathrm{■}$

  partiallyVisited: $v$ was reached via a tpq edge, and all of its unvisited neighbors are also reachable only via tpq edges.

• $\mathrm{■}$

  visited: $v$ has been visited but is not partiallyVisited or fullyVisited.

DFS_P1Tree() prioritizes edges at any node in the order: $\text{tp1}\succ \text{t11}\sim \text{t1q}\succ \text{tpq}$. The traversal proceeds like a standard DFS, moving forward to unvisited neighbors of visited nodes and backtracking from fullyVisited nodes. The key modification handles partiallyVisited nodes to ensure the P1Tree property. Suppose the DFS head reaches node $u$. The type of $u$ is determined by inspecting its neighbors $N(u)$. Based on the type of $u$, the DFS head proceeds as follows:

(D0)

All nodes are initially unvisited.

(D1)

If $u$ is fullyVisited, the DFS head backtracks to the parent of $u$.

(D2)

If $u$ is visited, the DFS head visits an unvisited neighbor of $u$ along the highest priority edge.

(D3)

If $u$ is partiallyVisited, the DFS head backtracks to the parent of $u$.

(D4)

A partiallyVisited node $u$ is treated as “re-visitable”. When the DFS traversal later reaches $u$ from a neighbor $w$ via an edge of type tp1 or t11, a reconfiguration occurs: the original parent edge of $u$ (which was of type tpq) is removed from the tree, and the new edge $\{w,u\}$ is added. The parent of $u$ is now swapped to $w$, and $u$’s type is changed to visited.

This parent-swap operation is crucial, and swapping the parent of a leaf does not create a cycle. This mechanism guarantees that every node eventually acquires a port-1 incident edge in the final tree. Figure 2 illustrates this process.

Agents collectively act as the “DFS head”. Initially, all agents are at a root node $v_0$ and are unsettled. The agent with the highest ID settles at $v_0$. The remaining unsettled agents form a scout pool. To decide the next move, these scouts perform a neighborhood search. When the DFS head moves to an unvisited node, the highest-ID unsettled agent settles there. This process continues, with agents settling at new nodes, until all unsettled agents have settled. The reconfiguration of partiallyVisited nodes is handled by the settled agent at that node, which updates its parent information when visited by the DFS head from its port-1 neighbor.

To perform neighborhood searches in $O(1)$ epochs, we need multiple agents to probe neighbor ports in parallel. We achieve this by designating certain nodes as vacated. The agent that would have stayed at a vacated node instead joins the scout pool and travels with the DFS head. A node’s state is either empty (not yet visited), occupied (an agent is settled and remains there), or vacated (settled agent is travelling with the DFS head). The decision to vacate is made locally based on the state of itself and its port-1 neighbor. Starting with an occupied root node, a node can become vacated if its port-1 neighbor is occupied and it is not acting as the port-1 neighbor for a previously vacated node. These rules are designed to ensure that information about a vacated node can be retrieved from a nearby occupied node, which is essential for the probing mechanism described next.

As established, the central challenge under asynchrony is distinguishing an empty node from a vacated one in constant time. Our Parallel_Probe() mechanism solves this directly. With a pool of scouts available (from vacated nodes and remaining unsettled agents), the DFS head can perform a neighborhood search in $O(1)$ epochs. Parallel_Probe() assigns available scouts to probe unexplored ports of the current node $x$. A scout agent $a$ traversing port $p_{xy}$ to a neighbor $y$ must determine if $y$ is occupied, vacated, or genuinely empty (i.e., unvisited by any DFS). The scout agent determines a node $x$ is empty by visiting the port-1 neighbor $y$ of $x$, and the port-1 neighbor $z$ of $y$ if $y$ is also empty. Each scout travels at most 3 edges away from $x$ and returns, taking a constant number of moves. Since there are at least $\lceil (k-2)/3\rceil$ scouts, all neighbors of a node can be probed in a constant number of parallel waves, thus taking $O(1)$ epochs.

The algorithm unfolds in two phases: exploration and retrace. In the exploration phase, agents build a P1Tree rooted at $v_0$ by traversing the graph and settling at nodes. At each node, the exploring DFS head checks if that node can be vacated or not. It settles an unsettled agent from the scout pool if the parallel neighborhood search finds an empty node. In the retrace phase, scouts return to their original nodes. The retrace works by having the agents move in a post-order traversal of the constructed P1Tree, detaching from the group when they reach their home nodes. The post-order traversal is possible due to the presence of parent information, the most recently visited child, and the immediate sibling of each settled agent. Given a group of settled agents, we prioritize the immediate sibling, then the most recently visited child. Afterwards, the child is detached. When no child remains, the agent group takes the port to reach the parent. Both phases take $O(k)$ epochs.

Summarizing the above discussion, we obtain the following results.

When agents start at multiple nodes, each group of co-located agents (a “multiplicity”) initiates its own independent instance of the rooted dispersion algorithm. Each exploration is identified by a unique “treelabel” based on its root agent’s ID. When two explorations meet (i.e., a scout from one tree probes a node occupied by an agent from another tree), a merger protocol is invoked. We call this GeneralAsync(). The merger strategy is based on a size-based subsumption rule. When exploration $T_1$ with $k_1$ agents meets $T_2$ with $k_2$ agents, the smaller exploration is absorbed by the larger one. For instance, if , all agents from $T_1$ (both settled and scouts) will abandon their exploration, gather at their root if possible, and then join the DFS head of $T_2$ as new unsettled agents. The larger exploration $T_2$ pauses briefly to absorb the new agents and then continues its DFS to find homes for them. This process ensures that the total number of agents in a single exploration grows monotonically. The overhead for collecting agents from an absorbed tree of size $k_i$ is $O(k_i)$. A careful analysis shows that the total time spent in mergers across the entire execution is bounded by $O(k)$, preserving the overall optimal time complexity. From the above discussion, we have the following results.