Anonymous Self-Stabilising Localisation via Spatial Population Protocols

Abstract In the distributed localisation problem (DLP), n anonymous robots (agents) A0, . . . ,An−1 are located at arbitrary points p0, . . . , pn−1 ∈ S, where S is a Euclidean space. Initially, each agent Ai operates within its own coordinate system in S, which may be inconsistent with those of other agents. The primary goal in DLP is for agents to reach a consensus on a unified (jointly agreed) coordinate system, in which all agents receive unique labels (coordinates) that accurately reflect the relative distances between all points p0, . . . , pn−1 in S. Extensive research on DLP has primarily focus on the feasibility and complexity of achieving consensus when agents have limited access to inter-agent distances, often due to missing or imprecise data. In contrast, this paper proposes a minimalist, computationally efficient distributed computing model where agents can query any pairwise relative positions, if needed. Specifically, we introduce a novel variant of population protocols, referred to as the spatial population protocols model. In this variant each agent can memorise one or a fixed number of coordinates, and when agents Ai and Aj interact, they can not only exchange their current knowledge but also either determine the distance dij between them in S (distance query model) or obtain the vector −→vij spanning points pi and pj (vector query model). We propose and analyse several distributed localisation protocols, including: 1. Leader-based localisation protocol with distance queries We propose and analyse two leader-based localisation protocols that stabilise silently in o(n) time. These protocols leverage an efficient solution to the novel concept of multi-contact epidemic, a natural generalisation of the core communication tool in population protocols, known as the one-way epidemic. 2. Self-stabilising leader localisation protocol with distance queries We show how to effectively utilise a leader election mechanism within the leader-based localisation protocol to get a DLP protocol that self-stabilises silently in time O(n(log n/n)1/(k+1) log n) in k-dimensions. 3. Self-stabilising localisation protocol with vector queries We propose and analyse an optimally fast DLP protocol which self-stabilises silently in O(log n) time.