Anonymous Self-Stabilising Localisation via Spatial Population Protocols

This paper presents a minimalist, efficient distributed computing model where randomly paired agents can query their relative positions upon meeting. Our focus is on achieving anonymity while maintaining high time efficiency and minimal use of network resources, including limited local storage (agent state space) and communication. To meet these goals, we introduce a new variant of population protocols, referred to as the spatial population protocols model.

The population protocol model originates from the seminal work by Angluin et al. [6]. This model provides tools for the formal analysis of pairwise interactions between indistinguishable entities known as agents, which have limited storage, communication, and computational capabilities. In a nutshell, population protocols comprise three major components: (1) a population of agents $A_0,\mathrm{\dots },A_{n-1}$, which are simple computational entities with limited states that interact in pairs; (2) interaction rules forming a transition function, which specify how agents update their states based on pairwise encounters; and (3) a (possibly random) scheduler of interactions, which determines the sequence of agent interactions, guiding the system toward a desired output or consensus. In self-stabilising protocols, the initial configuration of agents’ states is arbitrary. By contrast, non-self-stabilising protocols start with a predefined configuration encoding the input of the considered problem. A protocol concludes when it stabilises in a final configuration of states representing the solution of the considered problem. In the probabilistic variant of population protocols, which is also used here, the random scheduler selects an ordered pair of agents at each step, designated as the initiator and the responder, uniformly at random from the entire population. The asymmetry in this pair introduces a valuable source of random bits, which is utilised by population protocols. In this probabilistic setting, besides efficient state utilisation, time complexity is also a primary concern. It is often measured by the number of interactions, $ℐ$, required for the protocol to stabilise in a final configuration. More recently, the focus has shifted to parallel stabilisation time (or simply time), defined as $ℐ/n$, where $n$ is the population size. This measure captures the parallelism of independent, simultaneous interactions, which is leveraged in efficient population protocols that stabilise in time $O(\text{poly}\log n)$. All protocols introduced in this paper are stable (consistently correct), stabilise silently (agent states cease to change post-stabilisation), and guarantee stabilisation time with high probability (whp), defined as $1-n^{-\eta },$ for a constant $\eta >0$. Furthermore, our primary contribution, the localisation protocols detailed in Sections 3 and 4, exhibits self-stabilisation.

Among the primary tools in our localisation protocols, we emphasise the novel concept of multi-contact epidemic, see Section 2, a natural extension of the fundamental communication mechanism in population protocols, known as the one-way epidemic. Another key tool is leader election, a cornerstone of distributed computing that tackles the essential challenges of symmetry breaking, synchronisation, and coordination. In population protocols, the presence of a leader facilitates a more efficient computational framework [7]. However, achieving leader election within this model presents significant difficulties. Foundational results [16, 19] demonstrate that it cannot be solved in sublinear time if agents are restricted to a fixed number of states [20]. Further, Alistarh and Gelashvili [3] introduced a protocol stabilising in $O({\log }^{3}n)$ time with $O({\log }^{3}n)$ states. Later, Alistarh et al. [1] identified trade-offs between state use and stabilisation time, distinguishing slowly ($o(\log \log n)$ states) and rapidly stabilising ($O(\log n)$ states) protocols. Subsequent work achieved $O({\log }^{2}n)$ time whp and in expectation with $O({\log }^{2}n)$ states [13], later reduced to $O(\log n)$ states using synthetic coins [2, 12]. Recent research by Gąsieniec and Stachowiak reduced state usage to $O(\log \log n)$ while retaining $O({\log }^{2}n)$ time whp [26]. The expected time of leader election was further optimised to $O(\log n\log \log n)$ by Gąsieniec et al. in [27] and to the optimal time $O(\log n)$ by Berenbrink et al. in [11]. In contrast, self-stabilising leader election protocols present unique computational challenges. Notably, it was shown by Cai et al. in [15] that such protocols require at least $n$ states, in addition to knowledge of the exact value of $n$. Alternatively, if loose-stabilisation is allowed (where a leader remains in place for a long but finite time before re-election) an upper bound on $n$ may suffice, see work of Sudo et al. [40]. In [14, 21], it was established that any silently self-stabilising leader election protocol has an expected time complexity of at least $\mathrm{\Omega }(n)$. Furthermore, Burman et al. in [14] present silently self-stabilising protocols with expected time $O(n)$ and with high probability (whp) time $O(n\log n)$, both using $n+\mathrm{\Omega }(n)$ states. More recently, the space complexity of $O(n\log n)$-time leader election self-stabilising whp protocol has been improved to $n+O({\log }^{2}n)$ in [10] and to $n+O(\log n)$ in [25]. In this work, however, we employ a relatively straightforward leader election mechanism where each agent collects $\log n$ random bits, and a leader is determined by a complete set of $\log n$ 1s. This simple protocol ensures the election of a unique leader with constant probability. When repeated $O(\log n)$ times, this procedure guarantees unique leader election whp. For details see Section 3.

As previously discussed, the localisation problem is fundamental, with its many variants extensively studied over time. This work effectively integrates research in (distributed) localisation with rigidity theory of random geometric graphs, leveraging the increasingly popular population protocol model of computation. Surprisingly, little research has explored population protocols incorporating spatial properties, particularly those supporting geometric queries. The most relevant prior work focuses on efficient majority and leader election protocols for general toroidal grids [4] and self-stabilising leader election in rings [44, 45].

In this study, we assume agents are distributed in a $k$-dimensional space, where each interaction, viewed as a pairwise geometric query, results in an exchange of states (knowledge held by agents) augmented by information about the relative positions of the interacting agents. We present the following results.

In Section 2, we propose and analyse two leader-based localisation protocols in the model with distance queries. The first protocol (Algorithms 1) stabilises silently in time $O(n{(\log n/n)}^{1/(k+1)})$ whp (Theorem 4), in $k$-dimensional space. For $k=1,$ we present a faster protocol with the stabilisation time $O({(n\log n)}^{1/3})$ whp (Theorem 9). These two protocols leverage an efficient solution to the novel concept of multi-contact epidemic (Section 2.1), a natural generalisation of the core communication tool in population protocols, known as the one-way epidemic. In Section 3, we show how to effectively utilise leader election within the leader-based localisation protocol (Algorithm 1) in the model with distance queries. We propose and analyse a DLP protocol that self-stabilises silently in time $O(n{(\log n/n)}^{1/(k+1)}\log n)$ whp (Theorem 13), in $k$-dimensional space. Finally, in Section 4, we present surprisingly simple and optimally fast DLP protocol which self-stabilises silently in $O(\log n)$ time whp (Theorem 15), in the model with vector queries and fixed $k.$

For simplicity we assume that all geometric calculations are done via real arithmetic. Alternatively, one may assume that the actual positions of the agents are on vertices of a grid with integer coordinates, and, when determining the position of an agent, the agent can round the position up to the closest grid point.

We introduce and analyse the process of $\kappa$-contact epidemic (a multi-contact epidemic with a fixed parameter $\kappa$), a natural generalisation of epidemic dynamics in population protocols. In this process, the population initially contains at least $\kappa$ green agents, while the remaining agents are blue. A blue agent turns green after interacting with $\kappa$ distinct green agents. We show that the time complexity of this process is $O(n^{1-1/\kappa }\log n)$, for any fixed integer $\kappa$.

We start with two key lemmas that outline the progression of nominating green agents in the multi-contact epidemic.

The localisation protocol consists of two parts (see Algorithm 1). In Part 1: nomination process (lines 9-15), the leader nominates and labels $k$ agents, s.t., their labels (coordinates) span $k$-dimensional space in a common coordinate system. Their labels stabilise and agents become green. In Part 2: multilateration process (lines 16-22), the labels of all remaining (blue) agents become stable (green). And this happens when each remaining (blue) agent manages to interact with $k+1$ different green agents. This sequence of interactions enables each agent to position itself within a mutually agreed-upon coordinate system. Part 2 is based on a direct application of $\kappa$-contact epidemic, for $\kappa =k+1,$ as discussed in Section 2.1.

In Part 1, the positioning (labelling) of the first $k$ green agents requires nomination and approval from the leader, who maintains its private list of nominated green agents. More precisely, after an aspiring to become green agent $A_v$ manages to interact with all currently existing green agents. To become green $A_v$ must meet the leader and verify its list of green contacts to get nomination. Upon successful verification, the leader updates its list of green agents, and the new green agent $A_v$ is ready to calculate its projection onto the subspace spanned by its $i$ green predecessors and the leader, as well as its Euclidean distance from this subspace. Namely, the first $i$ coordinates of $A_v$’s label are determined by this projection, and the $(i+1)$-th coordinate (in the newly formed dimension) is equal to its distance from the aforementioned subspace. In Part 2, when positioning the remaining agents, we use the fact that interactions with $k+1$ green agents allow for the unambiguous determination of an agent’s position in the commonly agreed coordinate system.

In this section, we demonstrate how to enhance performance of Algorithm 1 on the line, i.e., within a linear space $S.$ While we focus on one dimension, our observations can be utilised also in higher dimensions. In what follows, we propose an alternative localisation protocol which positions agents not only by using 2-contact epidemic but also utilising interactions between agents with a single green contact on their list, coloured as greenish. In the new algorithm we take advantage of the fact that there are only two types of interactions between greenish agents not leading to positioning of both of them. The first type refers to interactions between agents that became greenish via contacting the same green agent. In the second, each of the two interacting greenish agents is at the same distance and on the same side of their unique green contact, rendering positioning impossible. We show that these types of interactions do not contribute significantly to the total time of the stabilisation.

We begin by analysing the memory utilisation of the protocol. The number of states required for leader election and buffering is $O(\log n)$, as shown in Lemma 10 and Lemma 21 of [25], respectively. However, agents occupying states used for leader election and buffering do not participate in the actual localisation process. As a result, the overall state space of the self-stabilising protocol is dominated by that of Algorithm 1, extended by a deadline counter of size $O\left(n{(\log n/n)}^{1/(k+1)}\right)$ used by the blue agents.

We begin by presenting a suitable leader election protocol that operates in $O(\log n)$ time and uses $O(\log n)$ space. This protocol is executed at the beginning of the first stage of each round and is followed by the main localisation protocol, Algorithm 1, augmented with anomaly detection and deadline counters.

Leader election is done by independently assigning a leader role to each agent with probability $p=\mathrm{\Theta }(1/n)$. In this way, the probability of electing exactly one leader is constant and is maximised when $p=1/n$ and is then approximately $1/e$. In our protocol, each agent independently tosses a symmetric coin $\log n$ times and becomes the leader if it gets heads on all tosses. We are left to describe the protocol implementing this process.

States in this protocol are denoted as pairs $(A,i)$, in which $A\in \{N,H,T\}$ and $i\in \{1,\mathrm{\dots },\log n,L,F\}$. The first component, $A$, represents the type of coin toss state: Neutral ($N$), Head ($H$), or Tails ($T$). The second component, $i$, either serves as a counter indicating progress toward successful leader election, or denotes a status: $L$ for leader and $F$ for follower. On leaving the buffering mechanism (the second stage of the previous round) all agents receive state $(N,1)$, and the only meaningful interactions in the leader election protocol are:

• $\mathrm{■}$

  The creation of $H:T$ state pairs ensuring that there are consistently the same number of agents with $H$ and $T$ states in the population: $(N,\ast )+(N,\ast )\to (H,\ast )+(T,\ast ).$

• $\mathrm{■}$

  A coin toss in which the initiator gets heads: $(\ast ,i)+(H,\ast )\to (\ast ,i+1)+(H,\ast ),$ if , and $(\ast ,\log n)+(H,\ast )\to (\ast ,L)+(H,\ast )$, otherwise.

• $\mathrm{■}$

  A coin toss in which the initiator gets tails: $(\ast ,i)+(T,\ast )\to (\ast ,F)+(T,\ast )$, if $i\in \{1,\mathrm{\dots },\log n\}$.

On the conclusion of the leader election process leader-based localisation (Algorithm 1) is executed, however, with a few modifications. Namely, the interaction counter with the deadline $O\left(n{(\log n/n)}^{1/(k+1)}\right)$ is added to every new blue agent. This is to ensure that the first stage does not exceed the expected stabilisation time of Algorithm 1. One also needs to manage anomaly detection. Recall, that two types of anomalies may arise. The first, label inconsistency, occurs only between two green agents. In particular, when all agents become green, this type of anomaly is detected in time $O(k\log n)$, see the lemma below.

The buffering for reset of the self-stabilising localisation protocol is solved in the same way as the buffering in the ranking protocol with $O(\log n)$ additional states from [25]. In this work, the signal for reset is the detection of an anomaly. It causes the state of the agents that performed the anomaly detection to be set to the first state of the buffer: $X_1$. The buffer is a line consisting of $2d\log n$ states: $X_1,X_2,\mathrm{\dots },X_{2d\log n}$ for $d$ large enough. We assign red colour to the states $X_1,\mathrm{\dots },X_{d\log n}$ and white (green in [25]) to the remaining buffer states.

We define the following transitions for these states:

• $\mathrm{■}$

  Progress on the line: $X_i+X_j\to X_{i+1}+X_{i+1}$ for $i\le j$.

• $\mathrm{■}$

  Reset propagation by red agents: $X_i+A\to X_1+X_1$, if $i\le d\log n$ and $A$ not on the line.

• $\mathrm{■}$

  Buffer departure by white agents: $X_{2d\log n}+X_{2d\log n}\to (N,1)+(N,1)$, where $(N,1)$ is the initial state of the leader election phase. Also $X_i+A\to (N,1)+A$, where $i>d\log n$ and $A$ is not on the line.

The analysis of the buffering process is summed up in the paper [25] by the following Lemma, proved there

If we substitute our $d$ for $d$ and $d^{\prime }$ in this lemma we obtain that at time $O(\log n)$ after the first agents appear in state $X_1$, all agents are white. On the other hand, when we substitute $2d$ for $d$ in the lemma and $d$ for $d^{\prime }$, we obtain that at time $O(\log n)$ the agents start to leave the line of the buffer.

We conclude Section 3 with the following theorem.