Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols

Kanaya, Haruki; Eguchi, Ryota; Sasada, Taisho; Inoue, Michiko

doi:10.4230/LIPIcs.OPODIS.2024.37

Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols

Haruki Kanaya

Nara Institute of Science and Technology, Japan Ryota Eguchi

Nara Institute of Science and Technology, Japan Taisho Sasada

Nara Institute of Science and Technology, Japan Michiko Inoue

Nara Institute of Science and Technology, Japan

Abstract

The population protocol model is a computational model for passive mobile agents. We address the leader election problem, which determines a unique leader on arbitrary communication graphs starting from any configuration. Unfortunately, self-stabilizing leader election is impossible to be solved without knowing the exact number of agents; thus, we consider loosely-stabilizing leader election, which converges to safe configurations in a relatively short time, and holds the specification (maintains a unique leader) for a relatively long time. When agents have unique identifiers, Sudo et al. (2019) proposed a protocol that, given an upper bound $N$ for the number of agents $n$ , converges in $O(mN\log n)$ expected steps, where $m$ is the number of edges. When unique identifiers are not required, they also proposed a protocol that, using random numbers and given $N$ , converges in $O(mN^{2}\log{N})$ expected steps. Both protocols have a holding time of $\Omega(e^{2N})$ expected steps and use $O(\log{N})$ bits of memory. They also showed that the lower bound of the convergence time is $\Omega(mN)$ expected steps for protocols with a holding time of $\Omega(e^{N})$ expected steps given $N$ .

In this paper, we propose protocols that do not require unique identifiers. These protocols achieve convergence times close to the lower bound with increasing memory usage. Specifically, given $N$ and an upper bound $\Delta$ for the maximum degree, we propose two protocols whose convergence times are $O(mN\log n)$ and $O(mN\log N)$ both in expectation and with high probability. The former protocol uses random numbers, while the latter does not require them. Both protocols utilize $O(\Delta\log N)$ bits of memory and hold the specification for $\Omega(e^{2N})$ expected steps.

Keywords and phrases:

Population protocols, Leader election, Loose-stabilization, Self-stabilization

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Distributed algorithms

Related Version:

Full Version: https://arxiv.org/abs/2411.03902

Funding:

The second author was supported by JSPS KAKENHI Grant Number 22H03569.

DOI:

10.4230/LIPIcs.OPODIS.2024.37

Event:

28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Editors:

Silvia Bonomi, Letterio Galletta, Etienne Rivière, and Valerio Schiavoni

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The population protocol model, introduced by Angluin et al. [3], is a computational model widely recognized in distributed computing and applicable to passive mobile sensor networks, chemical reaction systems, and molecular calculations, etc. This model comprises $n$ finite state machines (called agents), which form a network (called a population). Agents’ states are updated through communication (called interaction) among a pair of agents. A simple connected digraph $G=(V,E)$ (called a communication graph) determines the possibility of interaction among the agents. In this model, only one pair of agents interacts at each step. The interactions are determined by a uniform random scheduler.

The leader election problem is one of the most studied problems in population protocols. This problem involves agents electing a unique leader agent from the population and maintaining this unique leader forever. Angluin et al. [3] first studied this problem for complete graphs with designated common initial state. Under this assumption, many studies have been conducted [3, 6, 11, 17], and a time and space optimal protocol [6] has already been proposed. Several studies also exist for arbitrary graphs [1, 2], and a time-optimal protocol [2] has already been proposed.

The self-stabilizing leader election problem requires that agents start from any configuration, elect and externally maintain a unique leader agent. It is known that there is no self-stabilizing leader election protocol for arbitrary graphs [4] and complete graphs [8], and researchers have explored the problem in three ways. The first approach involves assuming that all agents initially know the exact number $n$ of agents [7, 8, 22]. The second approach introduces an oracle that informs agents about the existence of leaders [5, 9, 10]. The third approach relaxes the requirement of maintaining a unique leader forever, introducing a loosely-stabilizing leader election problem, where agents start from any configuration, elect a unique leader within a short time, and maintain this leader for a long time. Sudo et al. [16] first addressed this problem on complete graphs. Subsequent studies have continued to explore this problem [12, 15, 18, 19, 20, 21] as follows and summarized in Table 1.

Sudo, Ooshita, Kakugawa, and Masuzawa [18] first addressed this problem for arbitrary graphs, and it is significantly improved by Sudo, Ooshita, Kakugawa, Masuzawa, Datta, and Lawrence [20] introducing a novel concept of Same Speed Timer. They proposed two protocols. The first protocol, ${\mathcal{P}_{\mathrm{ID2}}}$ , assumes that agents have unique identifiers and are given $N$ as initial knowledge. ${\mathcal{P}_{\mathrm{ID2}}}$ converges within $O(mN\log{n})$ expected steps and holds the unique leader with $\Omega(Ne^{2N})$ expected steps, using $O(\log{N})$ bits of memory. The second protocol, ${\mathcal{P}_{\mathrm{RD2}}}$ , assumes that agents can make randomized transitions and is given $N$ as initial knowledge. ${\mathcal{P}_{\mathrm{RD2}}}$ converges within $O(mN^{2}\log{N})$ expected steps and holds the unique leader with $\Omega(Ne^{2N})$ expected steps using $O(\log{N})$ bits of memory. Sudo et al. also demonstrated that the lower bound of the convergence time is $\Omega(mN)$ steps for any loosely-stabilizing protocols with holding a unique leader $\Omega(e^{N})$ expected steps.

Loosely-stabilizing leader election protocols without requiring unique identifiers or random numbers were proposed [19] and then improved [22]. The protocol, $\mathcal{P}_{\mathrm{AR}}$ , given $N$ and $\Delta$ as initial knowledge, converges within $O(mnD\log{n}+mN\Delta^{2}\log{N})$ expected steps and holds with $\Omega(Ne^{N})$ expected steps using $O(\log{N})$ bits of memory [22].

Table 1: Convergence and Holding Times for Loosely-Stabilizing Leader Election Protocols with Exponential Holding Times.

n

denotes the number of agents,

N

denotes the upper bound of

n

,

m

denotes the number of edges of the communication graph,

D

denotes the diameter of the communication graph, and

\Delta

denotes the upper bound of the maximum degree of the communication graph. All protocols are given

N

as initial knowledge. Protocols with

\ast

are also given

\Delta

. The symbol

\dagger

represents lower bounds of convergence time or memory usage for protocols with holding time of

\Omega(e^{N})

.

	Graph	Convergence	Holding	Memory	Requisite
[16]	complete	$O(nN\log{n})$	$\Omega(Ne^{N})$	$O(\log{N})$	–
[12]	complete	$O(nN)$	$\Omega(e^{N})$	$O(\log{N})$	–
[12] $\dagger$	complete	$\Omega(nN)$	$\Omega(e^{N})$	–	–
[12] $\dagger$	complete	–	$\Omega(e^{N})$	$\Omega(\log{N})$	–
[18] $\ast$	arbitrary	$O(m\Delta N\log{n})$	$\Omega(Ne^{N})$	$O(\log{N})$	agent identifiers
[18] $\ast$	arbitrary	$O(m\Delta^{2}N^{3}\log{N})$	$\Omega(Ne^{N})$	$O(\log{N})$	random numbers
[20]	arbitrary	$O(mN\log{n})$	$\Omega(Ne^{2N})$	$O(\log{N})$	agent identifiers
[20]	arbitrary	$O(mN^{2}\log{N})$	$\Omega(Ne^{2N})$	$O(\log{N})$	random numbers
[20] $\dagger$	arbitrary	$\Omega(mN)$	$\Omega(e^{N})$	–	–
[19] $\ast$	arbitrary	$O(mnD\log{n}+mN\Delta^{2}\log{N})$	$\Omega(Ne^{N})$	$O(\log{N})$	–
This $\ast$	arbitrary	$O(mN\log{n})$	$\Omega(Ne^{2N})$	$O(\Delta\log{N})$	random numbers
This $\ast$	arbitrary	$O(mN\log{N})$	$\Omega(Ne^{2N})$	$O(\Delta\log{N})$	–

1.1 Our Contribution

In this paper, we propose a protocol ${\mathcal{P}_{\mathrm{BC}}}$ whose convergence time is nearly optimal on anonymous (without unique identifiers) arbitrary graphs, as supported by the lower bound [20]. The lower bound for the complete graph [12] is $\Omega(nN)$ , but this is a special case, as the lower bound [20] is known to hold even when $m=\Theta(n^{2})$ . Given $N$ and $\Delta$ , ${\mathcal{P}_{\mathrm{BC}}}$ converges within $O(mN\log n)$ steps if the transition is randomized, and $O(mN\log N)$ steps if the transition is deterministic¹¹1 Transition is said to be deterministic if it does not require random numbers in the transition. Though the transition is deterministic, we allow the protocol to exploit the randomness with which initiator and responder roles are chosen. , both in expectations and with high probability. The protocol holds the unique leader with $\Omega(Ne^{2N})$ expected steps and utilizes $O(\Delta\log N)$ bits of memory. The proposed ${\mathcal{P}_{\mathrm{BC}}}$ has better convergence time than SOTA self-stabilizing leader election protocol [22] which converges with $O(mn^{2}D\log{n})$ steps with requiring the knowledge of $n$ .

To achieve the convergence time of ${\mathcal{P}_{\mathrm{BC}}}$ , we utilize the Same Speed Timer proposed in ${\mathcal{P}_{\mathrm{RD2}}}$ [20], which requires two-hop coloring. The self-stabilizing two-hop coloring protocol was first studied by Angluin et al. [4], and further explored by Sudo et al. [20] (see Table 2). In this paper, we propose two new self-stabilizing two-hop coloring protocols; ${\mathcal{P}_{\mathrm{LRU}}}$ with randomized transitions, and ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ with deterministic transitions. Both protocols require $N$ and $\Delta$ as initial knowledge. ${\mathcal{P}_{\mathrm{LRU}}}$ converges within $O(mn)$ steps, both in expectation and with high probability, and uses $O(\Delta\log{N})$ bits of memory. ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ converges within $O(m(n+\Delta\log{N}))$ steps, both in expectation and with high probability, and also uses $O(\Delta\log{N})$ bits of memory. In ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ , agents generate random numbers independently from interactions among themselves. To ensure the independence among random numbers, we employ the self-stabilizing normal coloring protocol ${\mathcal{P}_{\mathrm{NC}}}$ to assign superiority or inferiority between adjacent agents. When interacting, only the superior agent uses the interaction to generate random numbers. ${\mathcal{P}_{\mathrm{NC}}}$ converges within $O(mn\log{n})$ steps, both in expectation and with high probability, and utilizes $O(\log{N})$ bits of memory.

Table 2: List of Convergence Times for Self-Stabilizing Two-Hop Coloring Protocols on Arbitrary Graphs.

n

denotes the number of agents,

N

denotes the upper bound of

n

,

m

denotes the number of edges of the communication graph,

\delta

denotes the maximum degree of the communication graph, and

\Delta

denotes the upper bound of

\delta

.

	Convergence	Memory	Knowledge	Requisite
Angluin et al. [4]	–	$O(\Delta^{2})$	$\Delta$	random numbers
Angluin et al. [4]	–	$O(\Delta^{2})$	$\Delta$	–
Sudo et al. [20]	$O(mn\delta\log{n})$	$O(\log{N})$	$N$	random numbers
${\mathcal{P}_{\mathrm{LRU}}}$ (this)	$O(mn)$	$O(\Delta\log{N})$	$N,\Delta$	random numbers
${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ (this)	$O(mn+m\Delta\log{N})$	$O(\Delta\log{N})$	$N,\Delta$	–

2 Preliminaries

In this paper, $\mathbb{N}$ denotes the set of natural numbers no less than one, and $\log{x}$ refers to $\log_{2}{x}$ . If we use the natural logarithm, we explicitly specify the base $e$ by writing $\log_{e}{x}$ .

A population is represented by a simple connected digraph $G=(V,E)$ , where $V$ ( $|V|\geq 2$ ) represents a set of agents, and $E\subseteq\{(u,v)\in V\times V\mid u\neq v\}$ represents the pairs of agents indicating potential interactions. An agent $u$ can interact with an agent $v$ if and only if $(u,v)\in E$ , where $u$ is the initiator and $v$ is the responder. We assume $G$ is symmetric, that is, if for every $(u,v)\in V\times V$ , the preposition $(u,v)\in E\Rightarrow(v,u)\in E$ holds. We also denote $n=|V|$ and $m=|E|$ . The diameter of $G$ is denoted by $D$ . The degree of agent $u$ is denoted by $\delta_{u}=|\{v\in V\mid(u,v)\in E\vee(v,u)\in E\}|$ , and the maximum degree is denoted by $\delta=\max_{u\in V}\{\delta_{u}\}$ . The upper bound $N$ of $n$ satisfies $N\geq n$ , and the upper bound $\Delta$ of $\delta$ satisfies $\delta\leq\Delta\leq 2(N-1)$ ²²2 Given only $N$ , $\delta\leq 2(N-1)$ holds, thus $\Delta\leq 2(N-1)$ . .

A protocol $\mathcal{P}$ is defined as a 5-tuple $(Q,Y,R,T,O)$ , where $Q$ represents the finite set of states of agents, $Y$ represents the finite set of output symbols, $R\subset\mathbb{N}$ represents the range of random numbers, $T:Q\times Q\times R\rightarrow Q\times Q$ is the transition function, and $O:Q\rightarrow Y$ is the output function. When an initiator $u$ , whose state is $p\in Q$ , interacts with a responder $v$ , whose state is $q\in Q$ , each agent updates their states via the transition function using their current states and a random number $r\in R$ to $p^{\prime},q^{\prime}\in Q$ such that $(p^{\prime},q^{\prime})=T(p,q,r)$ . An agent whose state is $p\in Q$ outputs $O(p)\in Y$ . A protocol $\mathcal{P}$ is with deterministic transitions if and only if $\forall r,\forall r^{\prime}\in R,\forall p,\forall q\in Q:T(p,q,r)=T(p,q,r^{% \prime})$ holds. Otherwise, a protocol $\mathcal{P}$ is with randomized transitions. The memory usage of protocol $\mathcal{P}$ is defined by $\lceil\log{|Q|}\rceil$ bits.

A configuration $C:V\rightarrow Q$ represents the states of all agents. The set of all configurations by protocol $\mathcal{P}$ is denoted by $\mathcal{C}_{all}(\mathcal{P})$ . A configuration $C$ transitions to $C^{\prime}$ by an interaction $e=(u,v)$ and a random number $r\in R$ if and only if $(C^{\prime}(u),C^{\prime}(v))=T(C(u),C(v),r)$ and $\forall w\in V\setminus\{u,v\}:C^{\prime}(w)=C(w)$ holds. Transitioning from a configuration $C$ to $C^{\prime}$ by an interaction $e$ and a random number $r$ is denoted by $C\xrightarrow{e,r}C^{\prime}$ . A uniform random scheduler $\Gamma=\Gamma_{0},\Gamma_{1},\dots$ determines which pair of agents interact at each step, where $\Gamma_{t}\in E$ (for $t\geq 0$ ) is a random variable satisfying $\forall(u,v)\in E,\forall t:\Pr(\Gamma_{t}=(u,v))=1/m$ . An infinite sequence of random numbers $\Lambda=R_{0},R_{1},\dots$ represents a random number generated at each step, where $R_{t}$ (for $t\geq 0$ ) is a random variable satisfying $\forall r\in R,\forall t:\Pr(R_{t}=r)=1/|R|$ . Given an initial configuration $C_{0}\in\mathcal{C}_{all}(\mathcal{P})$ , a uniform random scheduler $\Gamma$ , and a sequence of random numbers $\Lambda$ , the execution of protocol $\mathcal{P}$ is denoted by $\Xi_{\mathcal{P}}(C_{0},\Gamma,\Lambda)=C_{0},C_{1},\dots$ where $C_{t}\xrightarrow{\Gamma_{t},R_{t}}C_{t+1}$ (for $t\geq 0$ ) holds. If $\Gamma$ and $\Lambda$ are clear from the context, we may simply write $\Xi_{\mathcal{P}}(C_{0})$ . A set of configurations $\mathcal{S}$ is safe if and only if there is no configuration $C_{i}\notin\mathcal{S}\ (i\in\mathbb{N})$ for any configuration $C_{0}\in\mathcal{S}$ and any execution $\Xi(C_{0})=C_{0},C_{1},\dots$ . A protocol is silent if and only if there is no state changed after reached safe configurations.

For a protocol $\mathcal{P}$ that solves a population protocol problem, the expected holding time and the expected convergence time are defined as follows. The specification of the problem, which is a required condition for an execution, is denoted by $\mathscr{SC}$ . For any configuration $C\in\mathcal{C}_{all}(\mathcal{P})$ , any uniform random scheduler $\Gamma$ , and any infinite sequence of random numbers $\Lambda$ , the expected number of steps that an execution $\Xi_{\mathcal{P}}(C,\Gamma,\Lambda)$ satisfies $\mathscr{SC}$ is defined as the expected holding time, denoted $\mathrm{EHT}_{\mathcal{P}}(C,\mathscr{SC})$ . For any set of configurations $\mathcal{S}\subseteq\mathcal{C}_{all}(\mathcal{P})$ , any configuration $C\in\mathcal{C}_{all}(\mathcal{P})$ , any uniform random scheduler $\Gamma$ , and any infinite sequence of random numbers $\Lambda$ , the expected number of steps from the beginning of the execution $\Xi_{\mathcal{P}}(C,\Gamma,\Lambda)$ until the configuration reaches $\mathcal{S}$ is defined as the expected convergence time, denoted $\mathrm{ECT}_{\mathcal{P}}(C,\mathcal{S})$ . A computation is considered to be finished with high probability if and only if the computation finishes with probability $1-O(n^{-c})$ for $c\geq 1$ .

The leader election problem requires that all agents output either $L$ or $F$ , where $L$ represents a leader and $F$ represents a follower. The specification of the leader election is denoted by $L E$ . For an execution $\Xi_{\mathcal{P}}(C_{0})=C_{0},C_{1},\dots,C_{x},\dots$ , the configurations $C_{0},\dots,C_{x}$ satisfy $L E$ if and only if there is an agent $u$ such that $\forall i\in[0,x]:O(C_{i}(u))=L$ , and $\forall i\in[0,x],\forall v\in V\setminus\{u\}:O(C_{i}(v))=F$ holds.

Definition 1 (Loosely-stabilizing leader election[16]).

A protocol $\mathcal{P}$ is an $(\alpha,\beta)$ -loosely-stabilizing leader election protocol if and only if there exists a set of configurations $\mathcal{S}\subseteq\mathcal{C}_{all}(\mathcal{P})$ such that $\max_{C\in\mathcal{C}_{all}(\mathcal{P})}\mathrm{ECT}_{\mathcal{P}}(C,\mathcal% {S})\leq\alpha$ and $\min_{C\in\mathcal{S}}\mathrm{EHT}_{\mathcal{P}}(C,LE)\geq\beta$ holds.

A protocol $\mathcal{P}$ is a self-stabilizing protocol of a problem if and only if there exists safe configurations that any execution starting from any safe configuration satisfies the specification of the problem (called closure), and any execution starting from any configuration includes a safe configuration reaches the safe configurations (called convergence).

Definition 2.

A protocol $\mathcal{P}$ is a self-stabilizing normal coloring protocol if and only if there exists non-negative integer $x$ such that for any configuration $C_{0}\in\mathcal{C}_{all}(\mathcal{P})$ , and the execution $\Xi_{\mathcal{P}}(C_{0})=C_{0},C_{1},\dots,C_{x},\dots$ , the following condition holds: $\forall i\in\mathbb{N},\forall v\in V:O(C_{x}(v))=O(C_{x+i}(v))$ and $\forall v,\forall u\in V:(u,v)\in E\Rightarrow O(C_{x}(u))\neq O(C_{x}(v))$ .

Definition 3.

A protocol $\mathcal{P}$ is a self-stabilizing two-hop coloring protocols if and only if there exists non-negative integer $x$ such that for any configuration $C_{0}\in\mathcal{C}_{all}(\mathcal{P})$ , and the execution $\Xi_{\mathcal{P}}(C_{0})=C_{0},C_{1},\dots,C_{x},\dots$ , the following condition holds: $\forall i\in\mathbb{N},\forall v\in V:O(C_{x}(v))=O(C_{x+i}(v))$ and $\forall v,\forall u,\forall w\in V:(u,v)\in E\wedge(v,w)\in E\Rightarrow O(C_{% x}(u))\neq O(C_{x}(w))$ .

3 Self-Stabilizing Two-Hop Coloring

In this section, we introduce a self-stabilizing two-hop coloring protocol with randomized transitions ${\mathcal{P}_{\mathrm{LRU}}}$ , alongside a deterministic self-stabilizing two-hop coloring protocol with deterministic transitions ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ .

Two distinct agents $u,v\in V$ are called two-hop located if and only if there exists $w\in V$ such that $(u,w)\in E\wedge(v,w)\in E$ . A graph is considered two-hop colored if and only if, for any pair of agents $u$ and $v$ that are two-hop located, $u$ and $v$ are assigned distinct colors.

The basic strategy is similar to that described by Angluin et al. [4] and Sudo et al. [20]. The differences lie in the methods for generating colors and the length of the array used to record the colors of interacted agents. Angluin et al. memorized all generated colors using an array of length $\Delta(\Delta-1)+1$ , whereas Sudo et al. recorded only the most recent color. In the protocols, the agents record the last $\Delta$ colors.

We present a general strategy for color collision detection. When interacting two agents, they record each other’s color with a common binary random stamp. If there is no color collision, when they interact again they find that they remember each other’s color with the same stamp value. Assume that agents $v$ and $w$ have a color collision, that is, they are two-hop located with a common neighbor $u$ and have the same color. Consider the scenario in which interactions occur in the order of $(u,v)$ , $(u,w)$ , $(u,v)$ , and $u$ (resp. $v$ ) records $v$ ’s (resp. $u$ ’s) color with a stamp $0$ and then $u$ records $w$ ’s color (it is also $v$ ’s color) with a stamp $1$ . When $u$ and $v$ interact again, they notice they remember each other’s color with different stamp values and detect the color collision.

In both protocols, each agent has arrays whose size are $\Delta$ to record the last $\Delta$ colors and their stamps. Both protocols are the same except for the way to generate colors. In ${\mathcal{P}_{\mathrm{LRU}}}$ , agents generate colors by using the ability of generating uniform random numbers. In ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ , agents generate colors by using the roles of initiator and responder. To generate $x$ -digit binary random number, each agent generates a one random bit according to its role (initiator or responder) in each interaction, and repeats it $x$ times. To ensure the independence of random numbers, only one agent can use the interaction to generate random numbers for each interaction. To solve this issue, we use normal coloring. A graph is considered normal colored if and only if agents $u$ and $v$ are different colors for any pair $(u,v)\in E$ . We call agents’ colors which are colored by normal coloring the normal color. To guarantee independency among random numbers, when two agents interact, the agent with larger normal color value can use the interaction to generate random numbers. Though this mechanism does not give a chance to generate random numbers to agents with smaller normal color, random numbers are used when two agents detect a color collision. In such cases, two random numbers are provided as new colors from an agent who has larger normal color value and already generated two or more numbers.

3.1 Protocol ${\mathcal{P}_{\mathrm{LRU}}}$

In this subsection, we introduce the randomized self-stabilizing two-hop coloring protocol ${\mathcal{P}_{\mathrm{LRU}}}$ . Given $N$ and $\Delta$ , the protocol ${\mathcal{P}_{\mathrm{LRU}}}$ achieves convergence within $O(mn)$ steps, both in expectation and with high probability, while requiring $O(\Delta\log N)$ bits of memory per agent.

An agent $a$ in ${\mathcal{P}_{\mathrm{LRU}}}$ has four variables: $a.\mathtt{hopcolor}\in\{1,\dots,{8N^{3}\Delta^{2}}\}$ , $a.\mathtt{prev}\in\{1,\dots,\\ {8N^{3}\Delta^{2}}\}^{\Delta}$ , $a.\mathtt{stamp}\in\{0,1\}^{\Delta}$ , and $a.\mathtt{idx}\in\{0,\dots,\Delta\}$ . The variable $a.\mathtt{hopcolor}$ represents the two-hop color of the agent. The variable $a.\mathtt{prev}$ is an array that stores the last $\Delta$ colors interacted by the agent. The variable $a.\mathtt{stamp}$ is an array of size $\Delta$ , with each entry being either $0$ or $1$ , used to record the stamp associated with each color memorized. Lastly, $a.\mathtt{idx}$ serves as a temporary index to locate the color of the interacting agent in $a.\mathtt{prev}$ .

Algorithm 1 Self-Stabilizing two-hop coloring

\mathcal{P}_{LRU}

.

Outout Function

O

: Each agent

a

outputs

a.\mathtt{hopcolor}

.

when an initiator $a_{0}$ interacts with a responder $a_{1}$ do

1 forall $i\in\{0,1\}$ do

2

a_{i}.\mathtt{idx}\leftarrow 0

3 for $j\leftarrow 1\ \textnormal{{to}}\ \Delta$ do

4 if $a_{i}.\mathtt{prev}[j]=a_{1-i}.\mathtt{hopcolor}$ then

5

a_{i}.\mathtt{idx}\leftarrow j

6 break

7

8

9

10 Generate_Color ()

11 forall $i\in\{0,1\}$ do

12 if $a_{i}.\mathtt{idx}=0$ then

a_{i}.\mathtt{idx}\leftarrow\Delta

13 for $j\leftarrow a_{i}.\mathtt{idx}-1\ \textnormal{{downto}}\ 1$ do

14

(a_{i}.\mathtt{prev}[j+1],a_{i}.\mathtt{stamp}[j+1])\leftarrow(a_{i}.\mathtt{% prev}[j],a_{i}.\mathtt{stamp}[j])

15

16

17 Generate_Bit ()

18

function Generate_Color():

19 if $a_{0}.\mathtt{idx}>0\wedge a_{1}.\mathtt{idx}>0\wedge a_{0}.\mathtt{stamp}[a_{% 0}.\mathtt{idx}]\neq a_{1}.\mathtt{stamp}[a_{1}.\mathtt{idx}])$ then

20 generate two colors

c_{0},c_{1}\in\{1,...,8N^{3}\Delta^{2}\}

uniformly at random

21

(a_{0}.\mathtt{hopcolor},a_{1}.\mathtt{hopcolor})\leftarrow(c_{0},c_{1})

22

a_{0}.\mathtt{idx}\leftarrow a_{1}.\mathtt{idx}\leftarrow 0

23

24

function Generate_Bit():

25 generate bit

b\in\{0,1\}

uniformly at random

26

(a_{0}.\mathtt{prev}[1],a_{1}.\mathtt{prev}[1],a_{0}.\mathtt{stamp}[1],a_{1}.% \mathtt{stamp}[1])\leftarrow(a_{1}.\mathtt{hopcolor},a_{0}.\mathtt{hopcolor},b% ,b)

27

${\mathcal{P}_{\mathrm{LRU}}}$ is given by algorithm 1, and consists of four parts: i) reading memory, ii) collision detection, iii) saving colors, and iv) stamping.

i)

Reading memory (lines 1–6) aims to find a color of the interacting partner in an array of recorded colors. For each agent $a_{i}$ (where $i\in\{0,1\}$ ) interacting with another agent $a_{1-i}$ , $a_{i}$ searches $a_{i}.\mathtt{prev}$ for $a_{1-i}.\mathtt{hopcolor}$ and records the minimum index in $a_{i}.\mathtt{idx}$ if exists, otherwise, sets $a_{i}.\mathtt{idx}$ as $0$ .
ii)

Collision detection (lines 7, and 13–16) aims to generate new colors when a stamp collision is detected. To address this, two uniform random numbers are generated from the range $[1,{8N^{3}\Delta^{2}}]$ . These numbers are then used to update $a_{0}.\mathtt{hopcolor}$ and $a_{1}.\mathtt{hopcolor}$ respectively.
iii)

Saving colors (lines 8–11) aims to maintain arrays $\mathtt{prev}$ and $\mathtt{stamp}$ in a Least Recently Used (LRU) fashion.
iv)

Stamping (lines 12, and 17–18) aims to generate a common binary stamp to two interacting agents, and to move a color and a stamp of this current interacting partner to the heads of arrays $\mathtt{prev}$ and $\mathtt{stamp}$ .

We have following theorems.

Theorem 4.

Given the upper bound $N$ and $\Delta$ , ${\mathcal{P}_{\mathrm{LRU}}}$ is a self-stabilizing two-hop coloring protocol with randomized transitions, and the convergence time is $O(mn)$ steps both in expectation and with high probability.

Theorem 5.

Given the upper bound $N$ and $\Delta$ , ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ is a self-stabilizing two-hop coloring protocol with deterministic transitions, and converges to safe configurations within $O(m(n+\Delta\log{N}))$ steps both in expectation and with high probability.

4 Loosely-Stabilizing Leader Election

In this section, we propose a loosely-stabilizing leader election protocol ${\mathcal{P}_{\mathrm{BC}}}$ . ${\mathcal{P}_{\mathrm{BC}}}$ uses a self-stabilizing two-hop coloring protocol. Thus, if it uses ${\mathcal{P}_{\mathrm{LRU}}}$ , ${\mathcal{P}_{\mathrm{BC}}}$ is with randomized transitions. If it uses ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ , ${\mathcal{P}_{\mathrm{BC}}}$ is with deterministic transitions. In both cases, ${\mathcal{P}_{\mathrm{BC}}}$ holds a unique leader with $\Omega(Ne^{2N})$ expected steps and uses $O(\Delta\log{N})$ bits of memory. Note that ${\mathcal{P}_{\mathrm{BC}}}$ (with randomized transitions) always generates random numbers deterministically like in ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ outside of two-hop coloring since it does not affect a whole complexity.

The basic strategy of leader election is as follows: i) All agents become followers. ii) Some candidates of a leader emerge, and the number of candidates becomes $1$ with high probability. iii) If there are multiple leaders, return to i). Each agent $a$ has $6$ variables and $4$ timers: $a.\mathtt{LF}\in\{\mathtt{B},\mathtt{L}_{0},\mathtt{L}_{1},\mathtt{F}\}$ , $a.\mathtt{type}\in\{1,...,2^{\lceil\log{N}\rceil+1}-1\}$ , $a.\mathtt{id}\in\{1,...,2^{\lceil\log{N^{2}}\rceil+1}-1\}$ , $a.\mathtt{color}$ , $a.\mathtt{pcol}$ , $a.\mathtt{rc}$ $\in\{0,1\}$ , $a.\mathtt{timer}_{\mathtt{LF}}$ $\in[0,2\mathtt{t_{\mathrm{BC}}}]$ , $a.\mathtt{timer}_{\mathtt{KL}}\in[0,\mathtt{t_{\mathrm{BC}}}]$ , $a.\mathtt{timer}_{\mathrm{V}}\in[0,2\mathtt{t_{\mathrm{BC}}}]$ , and $a.\mathtt{timer}_{\mathrm{E}}\in[0,2\mathtt{t_{\mathrm{BC}}}]$ . Here, $\mathtt{t_{\mathrm{BC}}}$ is a sufficiently large value for ${\mathcal{P}_{\mathrm{BC}}}$ to work correctly. A status of an agent $a$ is represented by $a.\mathtt{LF}$ where $\mathtt{B}$ (leader candidate), $\mathtt{L}_{0}$ (leader mode), and $\mathtt{L}_{1}$ (duplication check mode) represent leaders and $\mathtt{F}$ represents a follower. The variable $a.\mathtt{type}$ is used for detecting multiple leaders. The variable $a.\mathtt{id}$ represents the identifier of leaders.

In ${\mathcal{P}_{\mathrm{BC}}}$ , agents mainly use the broadcast (also called the epidemic and the propagation) to inform others of something. In a broadcast mechanism, information from one agent is repeatedly copied (with modification if needed) to agents when two agents interact. In order to detect the end of operations (including broadcasts) for all agents, the agents uses timers. The timers decrease by Larger Time Propagation and Same Speed Timer. Using Larger Time Propagation and Same Speed Timer, all timer values decrease gradually, almost synchronously. Larger Time Propagation means that when an agent $u$ interacts with an agent $v$ , $u.\mathtt{timer}$ (resp. $v.\mathtt{timer}$ ) is set to $\max(u.\mathtt{timer},v.\mathtt{timer}-1)$ (resp. $\max(v.\mathtt{timer},u.\mathtt{timer}-1)$ ). A variable $a.\mathtt{rc}$ is used to implement Same Speed Timer and represents whether $a$ can decrease its own timers or not in the current interaction. Same Speed Timer decrease a timer value by $1$ when an agent interacts the same agent continuously. For Same Speed Timer, after reaching ${\mathcal{S}_{\mathrm{color}}}$ , the agents use the colors to determine whether the current partner is the last partner or not. A read-only variable $a.\mathtt{color}$ represents a color determined in the two-hop coloring. A variable $a.\mathtt{pcol}$ represents an agent’ color that $a$ interacted previously. The domains of $a.\mathtt{color}$ and $a.\mathtt{pcol}$ depend on a self-stabilizing two-hop coloring protocol. If we use ${\mathcal{P}_{\mathrm{LRU}}}$ , $a.\mathtt{color},a.\mathtt{pcol}\in\{1,\dots,8N^{3}\Delta^{2}\}$ . If we use ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ , $a.\mathtt{color},a.\mathtt{pcol}\in\{0,\dots,2^{\lceil\log{8N^{3}\Delta^{2}}% \rceil}-1\}$ .

4.1 Outline of ${\mathcal{P}_{\mathrm{BC}}}$

We show the outline of ${\mathcal{P}_{\mathrm{BC}}}$ . We call a configuration satisfying certain conditions a phase. ${\mathcal{P}_{\mathrm{BC}}}$ mainly has 3 phases: i) Global Reset, ii) Leader Generation, iii) Leader Detection. We first explain the overview of the three phases with the roles of $4$ timers using an example flow shown in Fig. 1, where the height of the timer represents the relative magnitude of its value.

i)

Global Reset is the phase that resets all agents when some inconsistencies are detected. (In Fig. 1(a), multiple leaders are detected.) A configuration is in the Global Reset if there exists agents whose $\mathtt{timer}_{\mathtt{KL}}>0$ . When some inconsistency is detected, a Global Reset phase is started and the kill virus is created. The kill virus makes an agent a follower, sets the agent’s identifier to $1$ (a tentative value before generating id), and also erases the search virus. The presence of kill virus is represented as a positive value of $\mathtt{timer}_{\mathtt{KL}}$ , which serves as timer to live (TTL). When the Global Reset phase begins, some agents’ $\mathtt{timer}_{\mathtt{KL}}$ are set to the maximum value and spread to all agents with decreasing the values as shown in Fig. 1(b). Eventually, $\mathtt{timer}_{\mathtt{KL}}$ will become $0$ , and the Global Reset phase will be finished. While $\mathtt{timer}_{\mathtt{KL}}>0$ , $\mathtt{timer}_{\mathtt{LF}}$ takes its maximum value and $\mathtt{timer}_{\mathrm{V}}$ takes 0.
ii)

Leader Generation is the phase where agents generate leaders. In ${\mathcal{P}_{\mathrm{BC}}}$ , a leader keeps a values of $\mathtt{timer}_{\mathtt{LF}}$ to its maximum value, while followers propagate the value with Larger Time Propagation and Same Speed Timer. If there is no leader (Fig. 1(c)), values of $\mathtt{timer}_{\mathtt{LF}}$ for some followers eventually become $0$ . Then these followers become candidates ( $\mathtt{B}$ ) (Fig. 1(d)). Each candidate for leaders generates a random number as an identifier using interactions. The way to generate random numbers is described in Section 3. The candidates broadcast their $\mathtt{id}$ s to all agents, and become a follower ( $\mathtt{F}$ ) if it encounters a larger $\mathtt{id}$ value. While generating an identifier ( $\mathtt{id}$ ), $\mathtt{timer}_{\mathrm{LF}}$ takes its maximum value, and it gradually decreases after generating $\mathtt{id}$ . When $\mathtt{timer}_{\mathrm{LF}}$ of a candidate becomes $0$ , it becomes a leader ( $\mathtt{L}_{0}$ ). When there are no candidates for leaders, Leader Generation is finished.
iii)

Leader Detection is the phase where leaders determine whether there are multiple leaders or not. The leaders generate search viruses periodically using $\mathtt{timer}_{\mathrm{E}}$ . When $\mathtt{timer}_{\mathrm{E}}$ becomes $0$ , the agent start generating a $\mathtt{type}$ of search virus. If there are multiple leaders, leaders generate search viruses almost simultaneously thanks to Larger Time Propagation. When leaders generate search viruses, they generate random numbers using interactions to determine the type of search virus. The type of search virus with its TTL $\mathtt{timer}_{\mathrm{V}}$ spreads to all agents. When two different types of search viruses meet, agents create the kill virus and move to the Global Reset phase (Fig. 1(a)). While, if there is a unique leader, one search virus is periodically generated and expired (Fig. 1(e)).

Phases circulates Global Reset, Leader Generation, and Leader Detection in this order. If there exists a unique leade , the configuration stays in Leader Detection phase with high probability. Otherwise, the phase moves to Global Reset phase. Timers $\mathtt{timer}_{\mathtt{KL}}$ and $\mathtt{timer}_{\mathtt{LF}}$ are used for Global Reset and Leader Generation phases to have enough steps.

Figure 1: An example flow of

{\mathcal{P}_{\mathrm{BC}}}

.

Algorithm 2 Loosely-Stabilizing Leader Election Protocol

{\mathcal{P}_{\mathrm{BC}}}

(1/3).

Output function

O

: An agent

a

outputs

\mathtt{L}

if

a.\mathtt{LF}\in\{\mathtt{B},\mathtt{L}_{0},\mathtt{L}_{1}\}

, otherwise,

\mathtt{F}

.

when an initiator $a_{0}$ interacts with a responder $a_{1}$ do

1 Execute self stabilizing two-hop coloring protocol

2

\textnormal{{REPEAT\_CHECK}}()

3 if $\exists i\in\{0,1\}:a_{i}.\mathtt{timer}_{\mathtt{KL}}>0$ then

\textnormal{{Reset}}()

4

\textnormal{{LARGER\_TIME\_PROPAGATE}}(\mathtt{KL})

5

\textnormal{{COUNT\_DOWN}}(\mathtt{KL})

6

\textnormal{{LARGER\_TIME\_PROPAGATE}}(\mathrm{E})

7

\textnormal{{COUNT\_DOWN}}(\mathrm{E})

8 if $a_{0}.\mathtt{LF},a_{1}.\mathtt{LF}\in\{\mathtt{L}_{0},\mathtt{L}_{1},\mathtt{% F}\}$ then

9

\textnormal{{LARGER\_TIME\_PROPAGATE}}(\mathtt{LF})

10

\textnormal{{COUNT\_DOWN}}(\mathtt{LF})

11

12 forall $i\in\{0,1\}$ do

13 if $a_{i}.\mathtt{LF}\in\{\mathtt{L}_{0},\mathtt{L}_{1}\}$ then

a_{i}.\mathtt{timer}_{\mathtt{LF}}\leftarrow\mathtt{t_{\mathrm{BC}}}

14

15

\textnormal{{GenerateLeader}}()

16

\textnormal{{Detect}}()

17

function LARGER_TIME_PROPAGATE( $x$ ):

18 if $\exists i\in\{0,1\}:a_{i}.\mathtt{timer}_{x}<a_{1-i}.\mathtt{timer}_{x}$ then

19

a_{i}.\mathtt{timer}_{x}\leftarrow a_{1-i}.\mathtt{timer}_{x}-1

20

21

function REPEAT_CHECK():

22 forall $i\in\{0,1\}$ do

23 if $a_{i}.\mathtt{pcol}=a_{1-i}.\mathtt{color}$ then

a_{i}.\mathtt{rc}\leftarrow 1

24 else

a_{i}.\mathtt{rc}\leftarrow 0

25

a_{i}.\mathtt{pcol}\leftarrow a_{1-i}.\mathtt{color}

26

27

function COUNT_DOWN( $x$ ):

28 forall $i\in\{0,1\}$ do

29 if $a_{i}.\mathtt{rc}=1$ then

a_{i}.\mathtt{timer}_{x}\leftarrow\max(0,a_{i}.\mathtt{timer}_{x}-1)

30

31

function Reset():

32 forall $i\in\{0,1\}$ do

33

(a_{i}.\mathtt{LF},a_{i}.\mathtt{id},a_{i}.\mathtt{timer}_{\mathrm{V}})% \leftarrow(\mathtt{F},1,0)

34

35

Algorithm 3 Loosely-Stabilizing Leader Election Protocol

{\mathcal{P}_{\mathrm{BC}}}

(2/3).

function GenerateLeader():

36 if $\exists i\in\{0,1\}:a_{i}.\mathtt{timer}_{\mathtt{KL}}>0$ then

37

a_{0}.\mathtt{timer}_{\mathtt{LF}}\leftarrow a_{1}.\mathtt{timer}_{\mathtt{LF}% }\leftarrow\mathtt{t_{\mathrm{BC}}}

// prevent starting GenerateLeader

38

39 if $\exists i\in\{0,1\}:a_{i}.\mathtt{LF}=\mathtt{F}\wedge a_{i}.\mathtt{timer}_{% \mathtt{LF}}=0$ then

40 if $a_{i}.\mathtt{id}\neq 1$ then

a_{0}.\mathtt{timer}_{\mathtt{KL}}\leftarrow a_{1}.\mathtt{timer}_{\mathtt{KL}% }\leftarrow\mathtt{t_{\mathrm{BC}}}

//

\mathtt{id}

hasn’t been reset

41 else

(a_{i}.\mathtt{LF},a_{i}.\mathtt{timer}_{\mathtt{LF}})\leftarrow(\mathtt{B},2% \mathtt{t_{\mathrm{BC}}})

// a new candidate is created

42

43 if $\forall i\in\{0,1\}:a_{i}.\mathtt{LF}=\mathtt{B}\wedge a_{i}.\mathtt{id}<2^{% \lceil\log{N^{2}}\rceil}$ then

44

(a_{1}.\mathtt{LF},a_{1}.\mathtt{id},a_{1}.\mathtt{timer}_{\mathtt{LF}})% \leftarrow(\mathtt{F},1,\mathtt{t_{\mathrm{BC}}})

45

46 if $\exists i\in\{0,1\}:a_{i}.\mathtt{LF}=\mathtt{B}\wedge a_{i}.\mathtt{id}<2^{% \lceil\log{N^{2}}\rceil}$ then

47

(a_{i}.\mathtt{id},a_{i}.\mathtt{timer}_{\mathtt{LF}})\leftarrow(2a_{i}.% \mathtt{id}+i,2\mathtt{t_{\mathrm{BC}}})

48

49 if $a_{0}.\mathtt{LF}\in\{\mathtt{F},\mathtt{B}\}\wedge a_{1}.\mathtt{LF}\in\{% \mathtt{F},\mathtt{B}\}\wedge(\exists i\in\{0,1\}:((a_{i}.\mathtt{LF}=\mathtt{% B}\wedge a_{i}.\mathtt{id}>2^{\lceil\log{N^{2}}\rceil})\vee a_{i}.\mathtt{LF}=% \mathtt{F})\wedge a_{i}.\mathtt{id}>a_{1-i}.\mathtt{id})$ then

50

(a_{1-i}.\mathtt{LF},a_{1-i},\mathtt{id})\leftarrow(a_{i}.\mathtt{LF},a_{i}.% \mathtt{id})

51

52 if $\exists i\in\{0,1\}:a_{i}.\mathtt{LF}=\mathtt{F}\wedge a_{1-i}.\mathtt{LF}=% \mathtt{B}$ then

53

a_{i}.\mathtt{timer}_{\mathtt{LF}}\leftarrow\mathtt{t_{\mathrm{BC}}}-1

// consider

a_{1-i}

as a leader

54

55 forall $i\in\{0,1\}$ do

56 if $a_{i}.\mathtt{LF}=\mathtt{B}\wedge a_{i}.\mathtt{rc}=1$ then

a_{i}.\mathtt{timer}_{\mathtt{LF}}\leftarrow\max(0,a_{i}.\mathtt{timer}_{% \mathtt{LF}}-1)

57 if $a_{i}.\mathtt{LF}=\mathtt{B}\wedge a_{i}.\mathtt{timer}_{\mathtt{LF}}=0$ then

(a_{i}.\mathtt{LF},a_{i}.\mathtt{timer}_{\mathtt{LF}})\leftarrow(\mathtt{L}_{0% },\mathtt{t_{\mathrm{BC}}})

58

59

Algorithm 4 Loosely-Stabilizing Leader Election Protocol

{\mathcal{P}_{\mathrm{BC}}}

(3/3).

function Detect():

60 if $\exists i\in\{0,1\}:a_{i}.\mathtt{LF}=\mathtt{B}$ then

61

a_{0}.\mathtt{timer}_{\mathrm{E}}\leftarrow a_{1}.\mathtt{timer}_{\mathrm{E}}% \leftarrow 2\mathtt{t_{\mathrm{BC}}}

// prevent starting Detect

62

63 forall $i\in\{0,1\}$ do

64 if $a_{i}.\mathtt{LF}\in\{\mathtt{L}_{0},\mathtt{L}_{1}\}\wedge a_{i}.\mathtt{% timer}_{\mathrm{E}}=0$ then

65

(a_{i}.\mathtt{LF},a_{i}.\mathtt{type},a_{i}.\mathtt{timer}_{\mathrm{E}})% \leftarrow(\mathtt{L}_{1},1,2\mathtt{t_{\mathrm{BC}}})

// start the type generation

66

67 if $a_{i}.\mathtt{LF}=\mathtt{L}_{1}\wedge a_{i}.\mathtt{type}<2^{\lceil\log{N}\rceil}$ then

68

(a_{i}.\mathtt{type},a_{i}.\mathtt{timer}_{\mathrm{E}})\leftarrow(2a_{i}.% \mathtt{type}+i,2\mathtt{t_{\mathrm{BC}}})

69 if $a_{i}.\mathtt{type}\geq 2^{\lceil\log{N}\rceil}$ then

70

a_{i}.\mathtt{timer}_{\mathrm{V}}\leftarrow 2\mathtt{t_{\mathrm{BC}}}

71

72

73

74 if $\exists i\in\{0,1\}:a_{i}.\mathtt{LF}=\mathtt{F}\wedge a_{1-i}.\mathtt{LF}\in% \{\mathtt{L}_{0},\mathtt{L}_{1}\}$ then

75 if $a_{i}.\mathtt{timer}_{\mathrm{V}}>0\wedge(a_{1-i}.\mathtt{LF}=\mathtt{L}_{0}% \vee a_{1-i}.\mathtt{type}<2^{\lceil\log{N}\rceil}\vee$

76

a_{i}.\mathtt{type}\neq a_{1-i}.\mathtt{type})

then

77

a_{0}.\mathtt{timer}_{\mathtt{KL}}\leftarrow a_{1}.\mathtt{timer}_{\mathtt{KL}% }\leftarrow\mathtt{t_{\mathrm{BC}}}

// different types are detected

78

79 else if $a_{i}.\mathtt{timer}_{\mathrm{V}}=0\wedge a_{1-i}.\mathtt{LF}=\mathtt{L}_{1}% \wedge a_{1-i}.\mathtt{timer}_{\mathrm{V}}>0$ then

80

(a_{i}.\mathtt{type},a_{i}.\mathtt{timer}_{\mathrm{V}})\leftarrow(a_{1-i}.% \mathtt{type},a_{1-i}.\mathtt{timer}_{\mathrm{V}}-1)

81

82

83 else if $a_{0}.\mathtt{LF}=\mathtt{F}\wedge a_{1}.\mathtt{LF}=\mathtt{F}$ then

84 if $a_{0}.\mathtt{timer}_{\mathrm{V}}>0\wedge a_{1}.\mathtt{timer}_{\mathrm{V}}>0% \wedge a_{0}.\mathtt{type}\neq a_{1}.\mathtt{type}$ then

85

a_{0}.\mathtt{timer}_{\mathtt{KL}}\leftarrow a_{1}.\mathtt{timer}_{\mathtt{KL}% }\leftarrow\mathtt{t_{\mathrm{BC}}}

// different types are detected

86

87 else if $\exists i\in\{0,1\}:a_{i}.\mathtt{timer}_{\mathrm{V}}=0\wedge a_{1-i}.\mathtt{% timer}_{\mathrm{V}}>0$ then

88

(a_{i}.\mathtt{type},a_{i}.\mathtt{timer}_{\mathrm{V}})\leftarrow(a_{1-i}.% \mathtt{type},a_{1-i}.\mathtt{timer}_{\mathrm{V}}-1)

89

90

91 else if $a_{0}.\mathtt{LF}\in\{\mathtt{L}_{0},\mathtt{L}_{1}\}\wedge a_{1}.\mathtt{LF}% \in\{\mathtt{L}_{0},\mathtt{L}_{1}\}$ then

92

a_{0}.\mathtt{timer}_{\mathtt{KL}}\leftarrow a_{1}.\mathtt{timer}_{\mathtt{KL}% }\leftarrow\mathtt{t_{\mathrm{BC}}}

// multiple leaders are detected

93

94

\textnormal{{LARGER\_TIME\_PROPAGATE}}(\mathrm{V})

95

\textnormal{{COUNT\_DOWN}}(\mathrm{V})

96 forall $i\in\{0,1\}$ do

97 if $a_{i}.\mathtt{timer}_{\mathrm{V}}>0$ then

a_{i}.\mathtt{timer}_{\mathrm{E}}\leftarrow 2\mathtt{t_{\mathrm{BC}}}

// prevent restarting Detect

98 if $a_{i}.\mathtt{LF}=\mathtt{L}_{1}\wedge a_{i}.\mathtt{timer}_{\mathrm{E}}<% \mathtt{t_{\mathrm{BC}}}/2$ then

a_{i}.\mathtt{LF}\leftarrow\mathtt{L}_{0}

99

100

4.2 Details of ${\mathcal{P}_{\mathrm{BC}}}$

${\mathcal{P}_{\mathrm{BC}}}$ is given by Algorithm 2, Algorithm 3, and Algorithm 4. We explain the details of ${\mathcal{P}_{\mathrm{BC}}}$ . ${\mathcal{P}_{\mathrm{BC}}}$ has five parts: i) Two-hop coloring, ii) Timer Count Down, iii) Reset, iv) Leader Generation, v) Leader Detection. The relationship between the three phases and five parts is as follows. The Global Reset phase corresponds to the Reset part, the Leader Generation phase to the Generate part, and the Leader Detection phase to the Detect part. The Timer Count Down part operates throughout all phases, while the Two-Hop Coloring part is completed before the phases begin. Throughout this explanation, we consider when an initiator $a_{0}$ interacts with a responder $a_{1}$ .

i)

In line 1, the agents execute the two-hop coloring protocol ${\mathcal{P}_{\mathrm{LRU}}}$ or ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ .
ii)

Timer Count Down (lines 2, 4–12, and 15–22) aims to increase or decrease timers. First, the interacting agents determine whether the current partner is the same as the last partner in REPEAT_CHECK (lines 2, and 17–20) to implement Same Speed Timer. After that, each agent saves the current partner’s color to its own $\mathtt{pcol}$ . Then, agents decrease timers if $a_{i}.\mathtt{rc}=1$ holds. $\mathtt{timer}_{\mathtt{KL}}$ (lines 4–5) and $\mathtt{timer}_{\mathrm{E}}$ (lines 6–7) are handled by Larger Time Propagation and Count Down. That is, for $i\in\{0,1\}$ , $a_{i}.\mathtt{timer}_{\mathtt{KL}}$ is set to $\max(a_{i}.\mathtt{timer}_{\mathtt{KL}},a_{1-i}.\mathtt{timer}_{\mathtt{KL}}-1)$ , and if $a_{i}.\mathtt{rc}=1$ holds, $a_{i}.\mathtt{timer}_{\mathtt{KL}}$ is decreased by 1 (resp. $\mathtt{timer}_{\mathrm{E}}$ ). If both interacting agents are not candidates ( $\mathtt{B}$ ), they increase or decrease $\mathtt{timer}_{\mathtt{LF}}$ like $\mathtt{timer}_{\mathtt{KL}}$ (lines 8–10). For $i\in\{0,1\}$ , if $a_{i}$ is a leader ( $\mathtt{L}_{0}$ or $\mathtt{L}_{1}$ ), $a_{i}.\mathtt{timer}_{\mathtt{LF}}$ is set to $\mathtt{t_{\mathrm{BC}}}$ (lines 11–12). If $a_{0}$ or $a_{1}$ is a candidate ( $\mathtt{B}$ ), $\mathtt{timer}_{\mathtt{LF}}$ increases or decreases in Leader Generation. $\mathtt{timer}_{\mathrm{V}}$ increases or decreases in Leader Detection.
iii)

Reset (lines 3, and 23–24) aims to reset the population when some inconsistency is detected. For $i\in\{0,1\}$ , if $a_{i}.\mathtt{timer}_{\mathtt{KL}}>0$ holds, $a_{i}$ sets $(a_{i}.\mathtt{LF},a_{i}.\mathtt{id},a_{i}.\mathtt{timer}_{\mathrm{V}})$ to $(\mathtt{F},1,0)$ . In other words, $a_{i}$ becomes a follower, its identifier becomes $1$ , and $a_{i}$ erases the search virus. This Reset is happened when and only when there are multiple leaders and candidates’ $\mathtt{id}$ have not been reset to $1$ . Specifically, when different search virus meets (lines 60–61, 65–66, 69–70), and when candidates’ $\mathtt{id}$ have not been reset (lines 27–28).
iv)

Generate Leader (lines 13, and 25–40) aims to generate a new leader when there are no leaders. For $i\in\{0,1\}$ , if $a_{i}.\mathtt{timer}_{\mathtt{KL}}>0$ holds, each agent sets $a_{i}.\mathtt{LF}$ to $\mathtt{t_{\mathrm{BC}}}$ to prevent starting Leader Generation during the Global Reset phase (lines 25–26). Firstly, for $i\in\{0,1\}$ , if $a_{i}.\mathtt{LF}$ becomes $0$ , $a_{i}$ determines that there are no leaders, and becomes a candidate for leaders ( $\mathtt{B}$ ) and sets $a_{i}.\mathtt{timer}_{\mathtt{LF}}$ to $2\mathtt{t_{\mathrm{BC}}}$ (lines 27–29). At this time, if $a_{i}.\mathtt{id}$ is not $1$ (i.e., , it has not been reset), $a_{i}$ sets $a_{i}.\mathtt{timer}_{\mathtt{KL}}$ to $\mathtt{t_{\mathrm{BC}}}$ and moves to the Global Reset phase (line 29). Secondly, candidates ( $\mathtt{B}$ ) generate random numbers as their own identifiers ( $\mathtt{id}$ ). For each interaction, if the candidate $u$ is an initiator, $u.\mathtt{id}$ is updated to $2u.\mathtt{id}$ ; otherwise, $u.\mathtt{id}$ is updated to $2u.\mathtt{id}+1$ until $u.\mathtt{id}$ becomes no less than $2^{\lceil\log{N^{2}}\rceil}$ (lines 32–33). For the independence of random numbers, if both agents are candidates and generating random numbers, the responder becomes a follower ( $\mathtt{F}$ ) by resetting $\mathtt{id}$ to $1$ (lines 30–31). Thirdly, if a candidate’s $\mathtt{id}$ becomes no less than $2^{\lceil\log{N^{2}}\rceil}$ , the candidate starts to broadcast its own $\mathtt{id}$ to other agents (lines 34–35). This broadcast allows all agents to know the maximum $\mathtt{id}$ of candidates. For $i\in\{0,1\}$ , if $a_{i}$ is a candidate and $a_{i}.\mathtt{id}<a_{1-i}.\mathtt{id}$ holds, $a_{i}$ becomes a follower ( $\mathtt{F}$ ) and sets $a_{i}.\mathtt{id}$ to $a_{1-i}.\mathtt{id}$ . For $i\in\{0,1\}$ , if $a_{i}$ is a follower and $a_{i}.\mathtt{id}>a_{1-i}.\mathtt{id}$ holds, $a_{1-i}$ sets $a_{1-i}.\mathtt{id}$ to $a_{i}.\mathtt{id}$ . To avoid generating new candidates when there are candidates in the population, for $i\in\{0,1\}$ , if $a_{i}$ is a follower and $a_{1-i}$ is a candidate, $a_{i}$ sets $a_{i}.\mathtt{timer}_{\mathtt{LF}}$ to $\mathtt{t_{\mathrm{BC}}}-1$ (lines 36–37). That is, we consider $a_{1-i}$ has $\mathtt{timer}_{\mathtt{LF}}=\mathtt{t_{\mathrm{BC}}}$ virtually. Eventually, all agents’ $\mathtt{id}$ s become the same, and most candidates become followers (and some candidates remain). The candidates measure until all candidates finish generating the $\mathtt{id}$ and $\mathtt{id}$ s are broadcast for a sufficiently long time using $\mathtt{timer}_{\mathtt{LF}}$ . A candidate decreases $\mathtt{timer}_{\mathtt{LF}}$ by 1 if the agent’s $\mathtt{rc}$ is $1$ (lines 39). Finally, when a candidate’s $\mathtt{timer}_{\mathtt{LF}}$ becomes $0$ , the candidate becomes a new leader ( $\mathtt{L}_{0}$ ) and sets $\mathtt{timer}_{\mathtt{LF}}$ to $\mathtt{t_{\mathrm{BC}}}$ (lines 40). The range of generated identifiers ( $\mathtt{id}$ ) is $[2^{\lceil\log{N^{2}}\rceil},2^{\lceil\log{N^{2}}\rceil+1})$ , so there exists a unique leader with high probability.
v)

Detect (lines 41–66) aims to determine whether there are multiple leaders or not. Leaders generate search viruses every time their $\mathtt{timer}_{\mathrm{E}}$ becomes $0$ . If $a_{0}$ or $a_{1}$ is a candidate ( $\mathtt{B}$ ), agents set their $\mathtt{timer}_{\mathrm{E}}$ to $2\mathtt{t_{\mathrm{BC}}}$ to prevent generating a search virus (lines 41–42). Firstly, for $i\in\{0,1\}$ , if $a_{i}$ is a leader ( $\mathtt{L}_{0}$ or $\mathtt{L}_{1}$ ) whose $\mathtt{timer}_{\mathrm{E}}$ becomes $0$ , $a_{i}$ becomes $\mathtt{L}_{1}$ and starts generating random numbers to get the type of search virus (lines 44–45). At the beginning of generating random numbers, $a_{i}$ sets $a_{i}.\mathtt{type}$ to $1$ . The way of generating random numbers is the same as $\mathtt{id}$ generation. While generating random numbers, a leader sets own $\mathtt{timer}_{\mathrm{E}}$ to $2\mathtt{t_{\mathrm{BC}}}$ to inform that there exist agents generating random numbers (lines 46–47). When a leader finished generating random numbers, the leader sets own $\mathtt{timer}_{\mathrm{V}}$ to $2\mathtt{t_{\mathrm{BC}}}$ (lines 48–49). Secondly, agents detect multiple leaders if there are multiple leaders. $\mathtt{L}_{1}$ broadcasts the generated search virus to all agents via some agents until $\mathtt{timer}_{\mathrm{V}}$ becomes $0$ (lines 50–59). If a follower having search virus and a leader not having search virus interact except the cases their types are same, they set $\mathtt{timer}_{\mathtt{KL}}$ to $\mathtt{t_{\mathrm{BC}}}$ and the phase moves to Global Reset (lines 51–52). If a follower not having search virus and a leader having search virus interact, the follower set own $\mathtt{timer}_{\mathrm{V}}$ to the leader’s $\mathtt{timer}_{\mathrm{V}}-1$ and set own $\mathtt{type}$ to the leader’s $\mathtt{type}$ (lines 53–54). If $a_{0}$ and $a_{1}$ are followers and they have different types of search viruses, they set $\mathtt{timer}_{\mathtt{KL}}$ to $\mathtt{t_{\mathrm{BC}}}$ and move to Global Reset phase (lines 56–57). If $a_{0}$ and $a_{1}$ are followers and there exists $a_{i},a_{1-i}$ agents satisfying $a_{i}.\mathtt{timer}_{\mathrm{V}}=0$ and $a_{1-i}.\mathtt{timer}_{\mathrm{V}}>0$ for $i\in\{0,1\}$ , $a_{i}.\mathtt{timer}_{\mathrm{V}}$ is set to $a_{1-i}.\mathtt{timer}_{\mathrm{V}}-1$ and $a_{i}.\mathtt{type}$ is set to $a_{1-i}.\mathtt{type}$ (lines 58–59). If $a_{0}$ and $a_{1}$ are leaders, they set $\mathtt{timer}_{\mathtt{KL}}$ to $\mathtt{t_{\mathrm{BC}}}$ and move to Global Reset phase (lines 60–61). Finally, both agents’ $\mathtt{timer}_{\mathrm{V}}$ run Larger Time Propagation and decrease by $1$ if $a_{i}.\mathtt{rc}=1$ holds (lines 62–63). For $i\in\{0,1\}$ , if $a_{i}.\mathtt{timer}_{\mathrm{V}}>0$ holds, $a_{i}.\mathtt{timer}_{\mathrm{E}}$ is set to $2\mathtt{t_{\mathrm{BC}}}$ to prevent generating a new search virus when there is a search virus in the population (line 65). For $i\in\{0,1\}$ , if $a_{i}$ is a leader and $a_{i}.\mathtt{timer}_{\mathrm{E}}$ becomes less than $\mathtt{t_{\mathrm{BC}}}/2$ , $a_{i}$ becomes $\mathtt{L}_{0}$ (line 66). The range of generating random numbers of types is $[2^{\lceil\log{N}\rceil},2^{\lceil\log{N}\rceil+1})$ , so when there are multiple leaders in the population, the types generated by leaders are not the same with high probability.

Lemma 6.

For any execution, all candidates’ $\mathtt{id}$ no less than $2^{\lceil\log{N^{2}}\rceil}$ are independent and uniform if they are started to be generated during the execution. All leaders’ $\mathtt{type}$ no less than $2^{\lceil\log{N}\rceil}$ are independent and uniform if they are generated from the beginning of this execution.

4.3 Analysis

In this subsection, we analyze the expected convergence time and the expected holding time of ${\mathcal{P}_{\mathrm{BC}}}$ . We assume $\tau\geq\max(2d,\lceil\log{N}\rceil/2,15+3\log{n})$ , and $\mathtt{t_{\mathrm{BC}}}=16\tau$ . We will prove the following equations under these assumptions:

$\max_{C\in{\mathcal{S}_{\mathrm{color}}}}\mathrm{ECT}_{\mathcal{P}_{\mathrm{BC% }}}(C,{\mathcal{S}_{\mathrm{LE}}})=O(m\tau\log{n})$ .

$\min_{C\in{\mathcal{S}_{\mathrm{LE}}}}\mathrm{EHT}_{\mathcal{P}_{\mathrm{BC}}}% (C,LE)=\Omega(\tau e^{\tau})$ .

Here, ${\mathcal{S}_{\mathrm{color}}}$ and ${\mathcal{S}_{\mathrm{LE}}}$ are the sets of configurations described later.

We define the sets of configurations to prove the above equations:

${\mathcal{S}_{\mathrm{color}}}$ is the safe configurations of the self-stabilizing two-hop coloring.

${\mathcal{S^{\prime}}_{\mathrm{color}}}\subset{\mathcal{S}_{\mathrm{color}}}$ is the set of configurations where each agent’s $\mathtt{pcol}$ is the same as the last interacted agent’s color.

${\mathcal{KL}_{\mathrm{zero}}}=\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}% \mid\forall v\in V:C(v).\mathtt{timer}_{\mathtt{KL}}=0\}$ .

${\mathcal{B}_{\mathrm{no}}}=\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}\mid% \forall v\in V:C(v).\mathtt{LF}\neq\mathtt{B}\}$ .

${\mathcal{L}_{\mathrm{one}}}=\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}\mid% |\{v\in V\mid C(v).\mathtt{LF}\in\{\mathtt{L}_{0},\mathtt{L}_{1}\}\}|=1\}$ .

${\mathcal{LF}_{\mathrm{qua}}}=\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}% \mid\forall v\in V:C(v).\mathtt{LF}\neq\mathtt{B}\Rightarrow C(v).\mathtt{% timer}_{\mathtt{LF}}\geq\mathtt{t_{\mathrm{BC}}}/2\}$ .

${\mathcal{L}_{\mathrm{v1}}}=\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}\mid% \exists v\in V:C(v).\mathtt{LF}=\mathtt{L}_{1}\}$ .

${\mathcal{V}_{\mathrm{clean}}}=\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}% \mid\forall v\in V:C(v).\mathtt{timer}_{\mathrm{V}}=0\}$ .

${\mathcal{V}_{\mathrm{make}}}=\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}% \mid\forall v\in V:(C(v).\mathtt{LF}=\mathtt{L}_{1}\Rightarrow C(v).\mathtt{% type}<2^{\lceil\log{N}\rceil})\wedge(C(v).\mathtt{LF}\neq\mathtt{L}_{1}% \Rightarrow C(v).\mathtt{timer}_{\mathrm{V}}=0)\}$ .

${\mathcal{V}_{\mathrm{only}}}=\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}% \mid\forall v,\forall u\in V:C(v).\mathtt{timer}_{\mathrm{V}}>0\wedge C(u).% \mathtt{timer}_{\mathrm{V}}>0\Rightarrow C(v).\mathtt{type}=C(u).\mathtt{type}% \}\cap\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}\mid\forall v\in V:C(v).% \mathtt{LF}=\mathtt{L}_{1}\Rightarrow C(v).\mathtt{type}\geq 2^{\lceil\log{N}\rceil}$ .

${\mathcal{E}_{\mathrm{half}}}=\{C\in{\mathcal{S^{\prime}}_{\mathrm{color}}}% \mid\forall v\in V:C(v).\mathtt{LF}\in\{\mathtt{L}_{0},\mathtt{L}_{1}\}% \Rightarrow C(v).\mathtt{timer}_{\mathrm{E}}\geq\mathtt{t_{\mathrm{BC}}}\}$ .

${\mathcal{S}_{\mathrm{LE}}}={\mathcal{B}_{\mathrm{no}}}\cap{\mathcal{L}_{% \mathrm{one}}}\cap{\mathcal{LF}_{\mathrm{qua}}}\cap{\mathcal{KL}_{\mathrm{zero% }}}\cap({\mathcal{V}_{\mathrm{clean}}}\cup({\mathcal{L}_{\mathrm{v1}}}\cap({% \mathcal{V}_{\mathrm{make}}}\cup{\mathcal{V}_{\mathrm{only}}})\cap{\mathcal{E}% _{\mathrm{half}}}))$ .

4.3.1 Expected Holding Time

Lemma 7.

Let $C_{0}\in{\mathcal{S}_{\mathrm{LE}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . If $\Pr(\forall i\in[0,2m\tau]:C_{i}\in LE\wedge C_{2m\tau}\in{\mathcal{S}_{% \mathrm{LE}}})=1-O(ne^{-\tau})$ holds, then $\min_{C\in{\mathcal{S}_{\mathrm{LE}}}}\mathrm{EHT}_{\mathcal{P}_{\mathrm{BC}}}% (C,LE)=\Omega(\tau e^{\tau})$ holds.

Proof.

Let $A=\min_{C_{0}\in{\mathcal{S}_{\mathrm{LE}}}}\mathrm{EHT}_{\mathcal{P}_{\mathrm% {BC}}}(C_{0},LE)$ . We assume that $C_{0},\dots,C_{2m\tau}\in LE\wedge C_{2m\tau}\in{\mathcal{S}_{\mathrm{LE}}}$ holds with probability at least $p=1-O(ne^{-\tau})$ . Then, We have $A\geq p(2m\tau+A)$ . Solving this inequality gives $A\geq 2m\tau/(1-p)=\Omega(\tau e^{\tau})$ . $\hfill\blacktriangleleft$

We say that an agent $u$ encounters a counting interaction when $u$ interacts with an agent $v$ such that $u.\mathtt{color}=v.\mathtt{pcol}$ holds.

Lemma 8.

Let $C_{0}\in{\mathcal{S^{\prime}}_{\mathrm{color}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . The probability that every agent encounters less than $\mathtt{t_{\mathrm{BC}}}/2$ counting interactions while $\Gamma_{0},\dots,\Gamma_{2m\tau-1}$ is at least $1-ne^{-\tau}$ .

Lemma 9.

Let $C_{0}\in{\mathcal{S^{\prime}}_{\mathrm{color}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . For any $x\in\{\mathtt{LF},\mathtt{KL},\mathrm{E},\mathrm{V}\}$ , and for any $y\geq\mathtt{t_{\mathrm{BC}}}/2$ such that $y$ is no more than the maximum value of the domain of $\mathtt{timer}_{x}$ , when $\exists v\in V:C_{0}(v).\mathtt{timer}_{x}\geq y$ holds, the probability that $\forall u\in V:C_{2m\tau}(u).\mathtt{timer}_{x}>y-\mathtt{t_{\mathrm{BC}}}/2$ holds is at least $1-2ne^{-\tau}$ .

Lemma 10.

Let $C_{0}\in{\mathcal{S^{\prime}}_{\mathrm{color}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . For any integer $\lambda>0$ , and any integer $x$ satisfying $\mathtt{t_{\mathrm{BC}}}\leq x\leq 2\mathtt{t_{\mathrm{BC}}}$ , if $\forall v\in V:C_{0}(v).\mathtt{timer}_{\mathtt{LF}}\geq x\wedge\forall i\in[0% ,\lambda-1],\exists v\in V:C_{2mi\tau}(v).\mathtt{timer}_{\mathtt{LF}}\geq x$ holds, then $\Pr(\forall j\in[0,2m\lambda\tau],\forall v\in V:C_{j}(v).\mathtt{timer}_{% \mathtt{LF}}>x-\mathtt{t_{\mathrm{BC}}}\wedge C_{2m\lambda\tau}(v).\mathtt{% timer}_{\mathtt{LF}}\geq x-\mathtt{t_{\mathrm{BC}}}/2)\geq 1-3\lambda ne^{-\tau}$ holds.

Proof.

Since there exists an agent $u$ satisfying $u.\mathtt{timer}_{\mathtt{LF}}\geq x$ in $C_{0}$ , the probability that every agent’s $\mathtt{timer}_{\mathtt{LF}}\geq x-\mathtt{t_{\mathrm{BC}}}/2$ holds in $C_{2m\tau}$ is at least $1-2ne^{-\tau}$ from Lemma 9. Since there is every agent $u$ satisfying $u.\mathtt{timer}_{\mathtt{LF}}\geq x-\mathtt{t_{\mathrm{BC}}}/2$ in $C_{0}$ , $\Pr(\forall j\in[0,2m\tau],\forall v\in V:C_{j}(v).\mathtt{timer}_{\mathtt{LF}% }>x-\mathtt{t_{\mathrm{BC}}})\geq 1-ne^{-\tau}$ holds from Lemma 8. Thus, $\Pr(\forall j\in[0,2m\tau],\forall v\in V:C_{j}(v).\mathtt{timer}_{\mathtt{LF}% }>x-\mathtt{t_{\mathrm{BC}}}\wedge C_{2m\tau}(v).\mathtt{timer}_{\mathtt{LF}}% \geq x-\mathtt{t_{\mathrm{BC}}}/2)\geq 1-3ne^{-\tau}$ holds by the union bound. Repeating this $\lambda$ times, we get $\Pr(\forall j\in[0,2m\lambda\tau],\forall v\in V:C_{j}(v)>x-\mathtt{t_{\mathrm% {BC}}}\wedge C_{2m\lambda\tau}(v).\mathtt{timer}_{\mathtt{LF}}\geq x-\mathtt{t% _{\mathrm{BC}}}/2)\geq 1-3\lambda ne^{-\tau}$ by the union bound. $\hfill\blacktriangleleft$

We can prove Lemma 11 by the same way of Lemma 10, and Lemma 12 by assigning $\lambda=1$ to Lemma 10. Lemma 13, 14, and 15 analyzes the probability that configuration keep some condition for some interval.

Lemma 11.

Let $C_{0}\in{\mathcal{S^{\prime}}_{\mathrm{color}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . For any integer $\lambda>0$ , and any integer $x$ satisfying $\mathtt{t_{\mathrm{BC}}}\leq x\leq 2\mathtt{t_{\mathrm{BC}}}$ , if $\forall v\in V:C_{0}(v).\mathtt{timer}_{\mathrm{E}}\geq x\wedge\forall i\in[0,% \lambda-1],\exists v\in V:C_{2mi\tau}(v).\mathtt{timer}_{\mathrm{E}}\geq x$ holds, then $\Pr(\forall i\in[0,2m\lambda\tau],\forall v\in V:C_{i}(v).\mathtt{timer}_{% \mathrm{E}}>x-\mathtt{t_{\mathrm{BC}}}\wedge C_{2m\lambda\tau}(v).\mathtt{% timer}_{\mathrm{E}}\geq x-\mathtt{t_{\mathrm{BC}}}/2)\geq 1-3\lambda ne^{-\tau}$ holds.

Lemma 12.

Let $C_{0}\in{\mathcal{S}_{\mathrm{LE}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . $\Pr(\forall i\in[0,2m\tau]:C_{i}\in{\mathcal{B}_{\mathrm{no}}}\wedge C_{2m\tau% }\in{\mathcal{LF}_{\mathrm{qua}}})\geq 1-3ne^{-\tau}$ holds.

Lemma 13.

Let $C_{0}\in{\mathcal{S}_{\mathrm{LE}}}\cap{\mathcal{V}_{\mathrm{clean}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . $\Pr(\forall i\in[0,2m\tau]:C_{i}\in{\mathcal{L}_{\mathrm{one}}}\wedge C_{2m% \tau}\in{\mathcal{S}_{\mathrm{LE}}}\cap({\mathcal{V}_{\mathrm{clean}}}\cup{% \mathcal{L}_{\mathrm{v1}}}\cap({\mathcal{V}_{\mathrm{make}}}\cup{\mathcal{V}_{% \mathrm{only}}})\cap{\mathcal{E}_{\mathrm{half}}})\geq 1-5ne^{-\tau}$ holds.

Lemma 14.

Let $C_{0}\in{\mathcal{S}_{\mathrm{LE}}}\cap{\mathcal{L}_{\mathrm{v1}}}\cap{% \mathcal{V}_{\mathrm{make}}}\cap{\mathcal{E}_{\mathrm{half}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . $\Pr(\forall i\in[0,2m\tau]:C_{i}\in{\mathcal{L}_{\mathrm{one}}}\wedge C_{2m% \tau}\in{\mathcal{S}_{\mathrm{LE}}}\cap{\mathcal{L}_{\mathrm{v1}}}\cap({% \mathcal{V}_{\mathrm{make}}}\cup{\mathcal{V}_{\mathrm{only}}})\cap{\mathcal{E}% _{\mathrm{half}}})\geq 1-3ne^{-\tau}$ holds.

Lemma 15.

Let $C_{0}\in{\mathcal{S}_{\mathrm{LE}}}\cap{\mathcal{L}_{\mathrm{v1}}}\cap{% \mathcal{V}_{\mathrm{only}}}\cap{\mathcal{E}_{\mathrm{half}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . $\Pr(\forall i\in[0,2m\tau]:C_{i}\in{\mathcal{L}_{\mathrm{one}}}\wedge C_{2m% \tau}\in{\mathcal{S}_{\mathrm{LE}}}\cap({\mathcal{V}_{\mathrm{clean}}}\cup{% \mathcal{L}_{\mathrm{v1}}}\cup{\mathcal{V}_{\mathrm{only}}}\cap{\mathcal{E}_{% \mathrm{half}}})\geq 1-5ne^{-\tau}$ holds.

Lemma 16.

$\min_{C\in{\mathcal{S}_{\mathrm{LE}}}}\mathrm{EHT}_{\mathcal{P}_{\mathrm{BC}}}% (C,LE)=\Omega(\tau e^{\tau})$ .

Proof.

Let $C_{0}\in{\mathcal{S}_{\mathrm{LE}}}$ . $\Pr(C_{0},\dots,C_{2m\tau}\in LE\wedge C_{2m\tau}\in{\mathcal{S}_{\mathrm{LE}}% })\geq 1-5ne^{-\tau}=1-O(ne^{-\tau})$ from Lemma 13, Lemma 14, and Lemma 15. Thus, this lemma follows from Lemma 7. $\hfill\blacktriangleleft$

4.3.2 Expected Convergence Time

We first analyze the number of interactions until all timers converge to $0$ with high probability. Let $\lambda\mathtt{t_{\mathrm{BC}}}$ be the maximum value of the domain of timers, that is, $\lambda=1$ for $\mathtt{timer}_{\mathtt{KL}}$ and $\lambda=2$ for $\mathtt{timer}_{\mathtt{LF}}$ , $\mathtt{timer}_{\mathrm{V}}$ , and $\mathtt{timer}_{\mathrm{E}}$ .

Lemma 17.

Let $C_{0}\in{\mathcal{S^{\prime}}_{\mathrm{color}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . For any $x\in\{\mathtt{LF},\mathtt{KL},\mathrm{V},\mathrm{E}\}$ , if every agent’s $\mathtt{timer}_{x}$ increases only by Larger Time Propagation (not including setting to a specific value like $\mathtt{t_{\mathrm{BC}}}$ by leaders etc.), the number of interactions until every agent’s $\mathtt{timer}_{x}$ becomes $0$ is less than $2340\lambda m\tau\log{n}$ with probability at least $1-e^{-\lambda\tau}$ .

Proof.

Let $z=\max_{v\in V}(C_{i}(v).\mathtt{timer}_{x})\ (i>0)$ . From the mechanism of Larger Time Propagation, for every agent $v$ , $C_{i}(v).\mathtt{timer}_{x}$ does not become $z$ if $C_{i-1}(v).\mathtt{timer}_{x}<z$ . Thus, when every agent decreases its timer by at least $1$ from $C_{j},\dots,C_{i}\ (0\leq j<i)$ , $\max_{v\in V}(C_{i}(v).\mathtt{timer}_{x})-\max_{v\in V}(C_{j}(v).\mathtt{% timer}_{x})\geq 1$ holds (i.e., , the maximum value of $\mathtt{timer}_{x}$ decreases by at least 1). Let $X\sim\text{Bi}(2m,\delta_{v}/m)$ be a binomial random variable that represents the number of interactions of an agent $v$ interacts during $2m$ interactions. From Chernoff Bound (Eq. 4.5 in [14]), $\Pr(X\geq\delta_{v})\geq\Pr(X>\delta_{v})=1-\Pr(X\leq\delta_{v})=1-\Pr(X\leq(1% -1/2)E[X])\geq 1-e^{-\delta_{v}/8}\geq 1-e^{-1/4}>1/5$ . Thus, the probability that an agent $v$ interacts no less than $\delta_{v}$ times during $2m$ interactions is at least $1/5$ . Let $Y\sim\text{Bi}(\delta_{v},2/\delta_{v})$ be a binomial random variable that represents the number of counting interactions that an agent $v$ encounters during $\delta_{v}$ interactions in which an agent $v$ interacts. The probability that $Y=0$ is $\Pr(Y=0)=(1-2\delta_{v})^{\delta_{v}}\leq e^{-2}<1/5$ . Thus, the probability that an agent $v$ encounters at least one counting interaction is at least $4/5$ . Let $E_{v}$ denote the number of interactions until an agent $v$ decreases its $\mathtt{timer}_{x}$ by at least $1$ . Since $E_{v}\leq 2m+(1-4/25)E_{v}$ holds, $E_{v}\leq 13m$ holds. By Markov’s inequality, the probability that an agent $v$ does not decrease $\mathtt{timer}_{x}$ during $2E_{v}$ interactions is no more than $1/2$ . Thus, the probability that an agent $v$ does not decrease $\mathtt{timer}_{x}$ during $4\log{n}\cdot E_{v}$ interactions is no more than $n^{-2}$ . By the union bound, the probability that every agent $v$ does not decrease $\mathtt{timer}_{x}$ during $4\log{n}\cdot E_{v}$ interactions is no more than $n^{-1}$ . Let $A$ be an event that every agent $v$ decreases $\mathtt{timer}_{x}$ by at least 1 during $4\log{n}\cdot E_{v}$ interactions. We consider the expected number of times until $A$ succeeds $16\lambda\tau(=\lambda\mathtt{t_{\mathrm{BC}}})$ times using geometric distributions. In other words, for $k\in[1,16\lambda\tau]$ , let $Z_{k}\sim Geom(p_{k})$ be the independent geometric random variable such that $p_{k}=1-1/n\geq 1/2$ . Considering the sum of independent random variables $Z=\sum_{k=1}^{16\lambda\tau}Z_{k}$ . Note that $E[Z]\leq 32\lambda\tau$ holds. From Janson’s inequality (Theorem 2.1 in [13]), $\Pr(Z\geq 45\lambda\tau)\leq\Pr(Z\geq 1.4\cdot 32\lambda\tau)\leq\Pr(Z\geq 1.4% \cdot E[Z])\leq e^{-p_{i}E[Z](1.4-1-\log_{e}{1.4})}\leq e^{-16\lambda\tau(1.4-% 1-\log_{e}{1.4})}\leq e^{-\lambda\tau}$ . Thus, the expected number of times that $A$ succeeds $16\lambda\tau$ times is less than $45\lambda\tau$ with probability at least $1-e^{-\lambda\tau}$ . Therefore, the number of interactions until all agents’ $\mathtt{timer}_{x}$ becomes $0$ is $45\lambda\tau\cdot 4\log{n}\cdot E_{v}\leq 2340\lambda m\tau\log{n}$ with probability at least $1-e^{-\lambda\tau}$ . $\hfill\blacktriangleleft$

Lemma 18 shows a convergence time.

Lemma 18.

Let $C_{0}\in{\mathcal{S}_{\mathrm{color}}}$ and $\Xi_{\mathcal{P}_{\mathrm{BC}}}(C_{0})=C_{0},C_{1},\dots$ . The number of interactions until the configuration reaches ${\mathcal{S}_{\mathrm{LE}}}$ is $O(m\tau\log{n})$ with probability $1-o(1)$ .

Theorem 19.

Protocol ${\mathcal{P}_{\mathrm{BC}}}$ is a randomized $(O(m(n+\tau\log{n})),\Omega(\tau e^{\tau}))$ -loosely-stabilizing leader election protocol for arbitrary graphs when $\tau\geq\max(2d,\lceil\log{N}\rceil/2,15+3\log{n})$ if ${\mathcal{P}_{\mathrm{LRU}}}$ is used for two-hop coloring.

Theorem 20.

Protocol ${\mathcal{P}_{\mathrm{BC}}}$ is a deterministic $(O(m(n+\Delta\log{N}+\tau\log{n})),\Omega(\tau e^{\tau}))$ -loosely-stabilizing leader election protocol for arbitrary graphs when $\tau\geq\max(2d,\lceil\log{N}\rceil/2,15+3\log{n})$ if ${\mathcal{P^{\prime}}_{\mathrm{LRU}}}$ is used for two-hop coloring.

5 Conclusion

New loosely-stabilizing leader election population protocols on arbitrary graphs without identifiers are proposed. One is randomized, and the other is deterministic. The randomized one converges within $O(mN\log{n})$ steps, while the deterministic one converges $O(mN\log{N})$ steps both in expectations and with high probability. Both protocols hold a unique leader with $\Omega(Ne^{2N})$ expected steps and utilizes $O(\Delta\log{N})$ bits of memory. The convergence time is close to the known lower bound of $\Omega(mN)$ .

References

[1] Dan Alistarh, Rati Gelashvili, and Joel Rybicki. Fast Graphical Population Protocols. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021), volume 217, pages 14:1–14:18, 2022. doi:10.4230/LIPICS.OPODIS.2021.14.
[2] Dan Alistarh, Joel Rybicki, and Sasha Voitovych. Near-optimal leader election in population protocols on graphs. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 246–256, 2022. doi:10.1145/3519270.3538435.
[3] Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235–253, 2006. doi:10.1007/S00446-005-0138-3.
[4] Dana Angluin, James Aspnes, Michael J. Fischer, and Hong Jiang. Self-stabilizing population protocols. ACM Trans. Auton. Adapt. Syst., 3(4), 2008. doi:10.1145/1452001.1452003.
[5] Joffroy Beauquier, Peva Blanchard, and Janna Burman. Self-stabilizing leader election in population protocols over arbitrary communication graphs. In Principles of Distributed Systems, pages 38–52, 2013. doi:10.1007/978-3-319-03850-6_4.
[6] Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 119–129, 2020. doi:10.1145/3357713.3384312.
[7] Janna Burman, Ho-Lin Chen, Hsueh-Ping Chen, David Doty, Thomas Nowak, Eric Severson, and Chuan Xu. Time-optimal self-stabilizing leader election in population protocols. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 33–44, 2021. doi:10.1145/3465084.3467898.
[8] Shukai Cai, Taisuke Izumi, and Koichi Wada. How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model. Theory of Computing Systems, 50(3):433–445, 2012. doi:10.1007/S00224-011-9313-Z.
[9] Davide Canepa and Maria Gradinariu Potop-Butucaru. Stabilizing leader election in population protocols. Research Report RR-6269, INRIA, 2007.
[10] Michael Fischer and Hong Jiang. Self-stabilizing leader election in networks of finite-state anonymous agents. In Principles of Distributed Systems, pages 395–409, 2006. doi:10.1007/11945529_28.
[11] Leszek Gąsieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 93–102, 2019. doi:10.1145/3323165.3323178.
[12] Taisuke Izumi. On space and time complexity of loosely-stabilizing leader election. In Structural Information and Communication Complexity, pages 299–312, 2015. doi:10.1007/978-3-319-25258-2_21.
[13] Svante Janson. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters, 135:1–6, 2018.
[14] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. doi:10.1017/CBO9780511813603.
[15] Yuichi Sudo, Ryota Eguchi, Taisuke Izumi, and Toshimitsu Masuzawa. Time-Optimal Loosely-Stabilizing Leader Election in Population Protocols. In 35th International Symposium on Distributed Computing (DISC 2021), volume 209, pages 40:1–40:17, 2021. doi:10.4230/LIPICS.DISC.2021.40.
[16] Yuichi Sudo, Junya Nakamura, Yukiko Yamauchi, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election in a population protocol model. Theoretical Computer Science, 444:100–112, 2012. doi:10.1016/J.TCS.2012.01.007.
[17] Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Time-optimal leader election in population protocols. IEEE Transactions on Parallel and Distributed Systems, 31(11):2620–2632, 2020. doi:10.1109/TPDS.2020.2991771.
[18] Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election on arbitrary graphs in population protocols. In Principles of Distributed Systems, pages 339–354, 2014. doi:10.1007/978-3-319-14472-6_23.
[19] Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely stabilizing leader election on arbitrary graphs in population protocols without identifiers or random numbers. IEICE Transactions on Information and Systems, E103.D(3):489–499, 2020. doi:10.1587/TRANSINF.2019FCP0003.
[20] Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K. Datta, and Lawrence L. Larmore. Loosely-stabilizing leader election for arbitrary graphs in population protocol model. IEEE Transactions on Parallel and Distributed Systems, 30(6), 2019. doi:10.1109/TPDS.2018.2881125.
[21] Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K. Datta, and Lawrence L. Larmore. Loosely-stabilizing leader election with polylogarithmic convergence time. Theoretical Computer Science, 806:617–631, 2020. doi:10.1016/J.TCS.2019.09.034.
[22] Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Self-stabilizing population protocols with global knowledge. IEEE Transactions on Parallel and Distributed Systems, 32(12):3011–3023, 2021. doi:10.1109/TPDS.2021.3076769.

[bib.bib1] [1] Dan Alistarh, Rati Gelashvili, and Joel Rybicki. Fast Graphical Population Protocols. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021), volume 217, pages 14:1–14:18, 2022. doi:10.4230/LIPICS.OPODIS.2021.14.

[bib.bib2] [2] Dan Alistarh, Joel Rybicki, and Sasha Voitovych. Near-optimal leader election in population protocols on graphs. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 246–256, 2022. doi:10.1145/3519270.3538435.

[bib.bib3] [3] Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235–253, 2006. doi:10.1007/S00446-005-0138-3.

[bib.bib4] [4] Dana Angluin, James Aspnes, Michael J. Fischer, and Hong Jiang. Self-stabilizing population protocols. ACM Trans. Auton. Adapt. Syst., 3(4), 2008. doi:10.1145/1452001.1452003.

[bib.bib5] [5] Joffroy Beauquier, Peva Blanchard, and Janna Burman. Self-stabilizing leader election in population protocols over arbitrary communication graphs. In Principles of Distributed Systems, pages 38–52, 2013. doi:10.1007/978-3-319-03850-6_4.

[bib.bib6] [6] Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 119–129, 2020. doi:10.1145/3357713.3384312.

[bib.bib7] [7] Janna Burman, Ho-Lin Chen, Hsueh-Ping Chen, David Doty, Thomas Nowak, Eric Severson, and Chuan Xu. Time-optimal self-stabilizing leader election in population protocols. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 33–44, 2021. doi:10.1145/3465084.3467898.

[bib.bib8] [8] Shukai Cai, Taisuke Izumi, and Koichi Wada. How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model. Theory of Computing Systems, 50(3):433–445, 2012. doi:10.1007/S00224-011-9313-Z.

[bib.bib9] [9] Davide Canepa and Maria Gradinariu Potop-Butucaru. Stabilizing leader election in population protocols. Research Report RR-6269, INRIA, 2007.

[bib.bib10] [10] Michael Fischer and Hong Jiang. Self-stabilizing leader election in networks of finite-state anonymous agents. In Principles of Distributed Systems, pages 395–409, 2006. doi:10.1007/11945529_28.

[bib.bib11] [11] Leszek Gąsieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 93–102, 2019. doi:10.1145/3323165.3323178.

[bib.bib12] [12] Taisuke Izumi. On space and time complexity of loosely-stabilizing leader election. In Structural Information and Communication Complexity, pages 299–312, 2015. doi:10.1007/978-3-319-25258-2_21.

[bib.bib13] [13] Svante Janson. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters, 135:1–6, 2018.

[bib.bib14] [14] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. doi:10.1017/CBO9780511813603.

[bib.bib15] [15] Yuichi Sudo, Ryota Eguchi, Taisuke Izumi, and Toshimitsu Masuzawa. Time-Optimal Loosely-Stabilizing Leader Election in Population Protocols. In 35th International Symposium on Distributed Computing (DISC 2021), volume 209, pages 40:1–40:17, 2021. doi:10.4230/LIPICS.DISC.2021.40.

[bib.bib16] [16] Yuichi Sudo, Junya Nakamura, Yukiko Yamauchi, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election in a population protocol model. Theoretical Computer Science, 444:100–112, 2012. doi:10.1016/J.TCS.2012.01.007.

[bib.bib17] [17] Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Time-optimal leader election in population protocols. IEEE Transactions on Parallel and Distributed Systems, 31(11):2620–2632, 2020. doi:10.1109/TPDS.2020.2991771.

[bib.bib18] [18] Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election on arbitrary graphs in population protocols. In Principles of Distributed Systems, pages 339–354, 2014. doi:10.1007/978-3-319-14472-6_23.

[bib.bib19] [19] Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely stabilizing leader election on arbitrary graphs in population protocols without identifiers or random numbers. IEICE Transactions on Information and Systems, E103.D(3):489–499, 2020. doi:10.1587/TRANSINF.2019FCP0003.

[bib.bib20] [20] Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K. Datta, and Lawrence L. Larmore. Loosely-stabilizing leader election for arbitrary graphs in population protocol model. IEEE Transactions on Parallel and Distributed Systems, 30(6), 2019. doi:10.1109/TPDS.2018.2881125.

[bib.bib21] [21] Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K. Datta, and Lawrence L. Larmore. Loosely-stabilizing leader election with polylogarithmic convergence time. Theoretical Computer Science, 806:617–631, 2020. doi:10.1016/J.TCS.2019.09.034.

[bib.bib22] [22] Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Self-stabilizing population protocols with global knowledge. IEEE Transactions on Parallel and Distributed Systems, 32(12):3011–3023, 2021. doi:10.1109/TPDS.2021.3076769.

Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Contribution

2 Preliminaries

Definition 1 (Loosely-stabilizing leader election[16]).

Definition 2.

Definition 3.

3 Self-Stabilizing Two-Hop Coloring

3.1 Protocol 𝓟𝐋𝐑𝐔

Theorem 4.

Theorem 5.

4 Loosely-Stabilizing Leader Election

4.1 Outline of 𝓟𝐁𝐂

4.2 Details of 𝓟𝐁𝐂

Lemma 6.

4.3 Analysis

4.3.1 Expected Holding Time

Lemma 7.

Proof.

Lemma 8.

Lemma 9.

Lemma 10.

Proof.

Lemma 11.

Lemma 12.

Lemma 13.

Lemma 14.

Lemma 15.

Lemma 16.

Proof.

4.3.2 Expected Convergence Time

Lemma 17.

Proof.

Lemma 18.

Theorem 19.

Theorem 20.

5 Conclusion

References

3.1 Protocol ${\mathcal{P}_{\mathrm{LRU}}}$

4.1 Outline of ${\mathcal{P}_{\mathrm{BC}}}$

4.2 Details of ${\mathcal{P}_{\mathrm{BC}}}$