Optimal Dispersion Under Asynchrony

The problem of dispersion of mobile agents studied extensively in recent distributed computing literature not only takes its inspiration from biological phenomena, such as damselfish establishing non-overlapping territories on coral reefs [6], or neural crest cells migrating and distributing themselves across the developing embryo [28]; but also with practical applications such as placing a fleet of small autonomous robots (agents) under shelves (nodes) in fulfillment centers [41]. It is also closely connected to other coordination tasks such as exploration, scattering, load balancing, and self-deployment [5, 10, 12, 14, 16, 39]. The dispersion problem, denoted as dispersion, involves k n mobile agents placed initially arbitrarily on the nodes of an n -node anonymous graph of maximum degree . The goal for the agents is to autonomously relocate such that each agent is on a distinct node of the graph (see Figure 1). The objective is to design algorithms that simultaneously optimize time and memory complexities. Time complexity is the total time required to achieve dispersion starting from any initial configuration. Memory complexity is the maximum number of bits stored in the persistent memory at each agent throughout the execution. We stress that graph nodes are memory-less and cannot store any information.