Dispersion of mobile robots on graphs in the asynchronous model
Ajay D. Kshemkalyani · Theoretical Computer Science · 2025
The dispersion problem on graphs requires k robots placed arbitrarily at the n nodes of an anonymous graph, where k ≤ n , to coordinate with each other to reach a final configuration in which each robot is at a distinct node of the graph. The dispersion problem is important due to its relationship to graph exploration by mobile robots, scattering on a graph, and load balancing on a graph. Prior work on solving dispersion assumed the synchronous model. We propose four algorithms to solve dispersion on graphs in the asynchronous model. The first two algorithms require O ( k log Δ ) bits at each robot and O ( min ( m , k Δ ) ) steps running time, where m is the number of edges and Δ is the maximum degree of the graph. The algorithms differ in what, where, and how data structures are maintained. The third algorithm has a space usage of O ( max ( min ( D , k ) ⋅ log Δ , log D ) ) bits at each robot and uses O ( Δ min ( D , k ) + 1 ) steps, where D is the graph diameter. The fourth algorithm has a space usage of O ( max ( log k , log Δ ) ) bits at each robot and uses O ( min ( m , k Δ ) ⋅ k ) steps. In contrast with existing works which all assume the synchronous model, these are the first algorithms to solve dispersion in the weaker but more realistic asynchronous model.