Dispersion of mobile robots on graphs in the asynchronous model

Abstract

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.