Saxena et al. prove precise exploration bounds for dynamic graphs with semi-synchronous agents
New results show exactly how many agents needed to explore changing networks under adversarial deactivation.
The article studies mobile agents exploring 1-interval connected dynamic graphs under a semi-synchronous scheduler. It proves exploration is impossible if an adversary deactivates at least ⌈k/(n-2)⌉ - 1 agents per round, even with unbounded memory, global communication, and full visibility. This yields an upper bound: exploration is solvable only when deactivation is at most ⌈k/(n-2)⌉ - 2. Achieving exploration at that threshold requires agents to have both 1-hop visibility and 1-hop communication. The article presents an exploration algorithm using k agents when deactivation is at most that bound, assuming 1-hop visibility and global communication, matching the adversarial bound from the impossibility results.
- Exploration is impossible if an adversary deactivates at least ⌈k/(n-2)⌉ - 1 agents per round in 1-interval connected dynamic graphs with n nodes and k agents.
- The matching algorithm achieves exploration when deactivation is at most ⌈k/(n-2)⌉ - 2 agents per round, requiring only 1-hop visibility and global communication.
- The work provides tight upper and lower bounds for semi-synchronous exploration, proving necessary conditions for agent capabilities (1-hop visibility and communication) at the threshold.
Why It Matters
Establishes fundamental limits for autonomous agent teams exploring unpredictable networks, directly impacting distributed robotics and resilient communication systems.