We study the self-stabilizing leader election (SS-LE) problem in the population protocol model, assuming exact knowledge of the population size n. Burman, Chen, Chen, Doty, Nowak, Severson, and Xu [BCC+21] (PODC) showed that this problem can be solved in O(n) expected time with O(n) states. Recently, Gąsieniec, Grodzicki, and Stachowiak [GGS25] (PODC) proved that n + O (log n) states suffice to achieve O(n log n) time both in expectation and with high probability (w.h.p.). If substantially more states are available, sublinear time can be achieved. The authors of [BCC+21] presented a 2O(nρ)-state SS-LE protocol with a parameter ρ: setting ρ = Θ(log n) yields an optimal O(log n) time both in expectation and w.h.p., while ρ = Θ(1) results in O(ρn1/(ρ+1)) expected time. Recently, Austin, Berenbrink, Friedetzky, Götte, and Hintze [ABF+25] (PODC) presented a novel SS-LE protocol parameterized by a positive integer ρ with 1 ≤ ρ < n/2 that solves SS-LE in O(n/ρ · log n) time w.h.p. using 2O(ρ2 log n) states. This paper independently presents yet another time-space tradeoff of SS-LE: for any positive integer ρ with 2≤ρ≤n, SS-LE can be achieved within O(n/ρ · log ρ) expected time using 22ρlg2 ρ + O(log n) states. The proposed protocol uses significantly fewer states than [ABF+25] for any expected stabilization time above Θ(nlog⁡n). When ρ = Θ(log n/log2 log n), the proposed protocol is the first to achieve sublinear time while using only polynomially many states. A limitation of our protocol is that the constraint ρ≤n prevents achieving o(nlog⁡n) time, whereas the protocol of [ABF+25] can surpass this bound.

This paper addresses the collision detection problem in population protocols. The network consists of state machines called agents. At each time step, exactly one pair of agents is chosen uniformly at random to interact, updating their states. The collision detection problem assumes that each agent starts with an input integer between 1 and n , where n is the number of agents, and requires the agents to determine whether there are any duplicate input values among them. Specifically, the goal is for all agents to output false if all input values are distinct, and true otherwise. This paper presents an algorithm that solves this problem in sublinear parallel time, both with high probability and in expectation, using only a polynomial number of states, thereby answering one of the open questions raised by Burman, Chen, Chen, Doty, Nowak, Severson, and Xu [PODC 2021].

In this paper, we consider the partial gathering problem of mobile agents in synchronous dynamic bidirectional ring networks. The partial gathering problem is a generalization of the (well-investigated) total gathering problem, which requires that all k agents distributed in the network terminate at a non-predetermined single node. The partial gathering problem requires, for a given positive integer g ( < k ), that agents terminate in a configuration such that either at least g agents or no agent exists at each node. When k ≥ 2 g , the requirement for the partial gathering problem is strictly weaker than that for the total gathering problem, and thus it is interesting to clarify the difference in the move complexity between them. So far, the partial gathering problem has been considered in static graphs. In this paper, we start considering partial gathering in dynamic graphs. As a first step, we consider this problem in 1-interval connected rings, that is, one of the links in a ring may be missing at each time step. In such networks, focusing on the relationship between the values of k and g , we fully characterize the solvability of the partial gathering problem and analyze the move complexity of the proposed algorithms when the problem can be solved. First, we show that the g -partial gathering problem is unsolvable when k ≤ 2 g . Second, we show that the problem can be solved with O ( n log g ) time and the total number of O ( gn log g ) moves when 2 g + 1 ≤ k ≤ 3 g − 2 . Third, we show that the problem can be solved with O ( n ) time and the total number of O ( kn ) moves when 3 g − 1 ≤ k ≤ 8 g − 4 . Notice that since k = O ( g ) holds when 3 g − 1 ≤ k ≤ 8 g − 4 , the move complexity O ( kn ) in this case can be represented also as O ( gn ). Finally, we show that the problem can be solved with O ( n ) time and the total number of O ( gn ) moves when k ≥ 8 g − 3 . These results mean that the partial gathering problem can be solved also in dynamic rings when k ≥ 2 g + 1 . In addition, agents require a total number of Ω( gn ) (resp., Ω( kn )) moves to solve the partial (resp., total) gathering problem. Thus, when k ≥ 3 g − 1 , agents can solve the partial gathering problem with the asymptotically optimal total number of O ( gn ) moves, which is strictly smaller than that for the total gathering problem.

In this paper, we present two self-stabilizing algorithms that enable a single (mobile) agent to explore graphs. Starting from any initial configuration, i.e., regardless of the initial states of the agent and all nodes, as well as the initial location of the agent, the algorithms ensure the agent visits all nodes. We evaluate the algorithms based on two metrics: the cover time , defined as the number of moves required to visit all nodes, and memory usage , defined as the storage needed for maintaining the states of the agent and each node. The first algorithm is randomized. Given an integer c = Ω ( n ) , its cover time is optimal, i.e., O ( m ) in expectation, and its memory requirements are O (log c ) bits for the agent and O ( log ( c + δ v ) ) bits for each node v , where n and m are the numbers of nodes and edges, respectively, and δ v is the degree of node v . For general c ≥ 2, its cover time is O ( m · min ( D , n c + 1 , D c + log n ) ) , where D is the diameter of a graph. The second algorithm is deterministic. It requires an input integer k ≥ max ( D, δ max ), where δ max is the maximum degree of the graph. The cover time of this algorithm is O ( m + n D ) , and it uses O (log k ) bits of memory for both the agent and each node.

In this paper, we address the problem of uniformly deploying mobile robots in complete bipartite graphs. Specifically, when n robots are positioned arbitrarily at distinct nodes in a complete bipartite graph K_{n,n}, which consists of two n-node sets V_L and V_R, the uniform deployment problem requires the robots to achieve one of the following configurations: (a) each node in V_L is occupied by exactly one robot, with no robots in V_R, or (b) each node in V_R is occupied by exactly one robot, with no robots in V_L. In either configuration, the distance between any two robots is 2, ensuring that the robots are uniformly deployed. In this paper, we explore the relationship between the visibility range of robots and the solvability of the uniform deployment problem. First, we characterize solvable and unsolvable initial configurations under the assumption that robots have an infinite visibility range. Next, we demonstrate that visibility range 1 (meaning robots can only observe nodes at a distance of 1 and the robots positioned on them) is insufficient, proving the impossibility of solving the problem under this constraint. Conversely, we show that visibility range Θ(log n) is sufficient by presenting an algorithm that solves the uniform deployment problem in O(1) rounds, starting from any solvable initial configuration. Finally, we briefly introduce an example showing that robots with a constant visibility range (which is 3 in this example) cannot solve the problem in a native way.

Recently, Böckenhauer, Frei, Unger, and Wehner (SIROCCO 2023) introduced a novel variant of the graph exploration problem in which a single memoryless agent must visit all nodes of an unknown, undirected, and connected graph before returning to its starting node. Unlike the standard model for mobile agents, edges are not labeled with port numbers. Instead, the agent can color its current node and observe the color of each neighboring node. To move, it specifies a target color and then moves to an adversarially chosen neighbor of that color. Böckenhauer~et al.~analyzed the minimum number of colors required for successful exploration and proposed an elegant algorithm that enables the agent to explore an arbitrary graph using only eight colors. In this paper, we present a novel graph exploration algorithm that requires only six colors. Furthermore, we prove that five colors are sufficient if we consider only a restricted class of graphs, which we call the $φ$-free graphs, a class that includes every graph with maximum degree at most three and every cactus.

Abstract In this paper, we consider the partial gathering problem of mobile agents in dynamic tori. This problem requires $k$ agents distributed in the network to reach a configuration such that either at least $g$ agents or no agent exists at each node. Thus far, in dynamic graphs, partial gathering is considered in 1-interval connected rings, where one of the links in the ring may be missing at each time step. In this paper, we consider another dynamic topology. Concretely, we consider partial gathering in $n\times n$ dynamic tori such that each of the row and column rings is represented as a 1-interval connected ring. In such networks, when $k = O(gn)$, focusing on the relationship between the values of $k, n$, and $g$, we characterize the solvability of the problem and analyze the move complexity. First, we show that agents cannot solve the problem when $k = o(gn)$. Second, we show that agents can achieve partial gathering with a total number of $O(gn^{3})$ moves when $2gn+2n-1\le k \le 2gn + 6n +16g -12$. Finally, we show that agents can achieve partial gathering with a total number of $\Theta (gn^{2})$ moves when $k\ge 2gn + 6n +16g -11$.

We investigate crash-tolerant perpetual exploration algorithms by myopic luminous robots on ring networks. Myopic robots mean that they can observe nodes only within a certain fixed distance ϕ, and luminous robots mean that they have light devices that can emit a color from a set of colors. The goal of perpetual exploration is to ensure that robots, starting from specific initial positions and colors, move in such a way that every node is visited by at least one robot infinitely often. As a main contribution, we clarify the tight necessary and sufficient number of robots to realize perpetual exploration when at most f robots crash. In the fully synchronous model, we prove that f+2 robots are necessary and sufficient for any ϕ ≥ 1. In the semi-synchronous and asynchronous models, we prove that 3f+3 (resp., 2f+2) robots are necessary and sufficient if ϕ = 1 (resp., ϕ ≥ 2).

Research on distributed computing by a team of identical mobile computational entities, called robots, operating in a Euclidean space in $\mathit{Look}$-$\mathit{Compute}$-$\mathit{Move}$ ($\mathit{LCM}$) cycles, has recently focused on better understanding how the computational power of robots depends on the interplay between their internal capabilities (i.e., persistent memory, communication), captured by the four standard computational models (OBLOT, LUMI, FSTA, and FCOM) and the conditions imposed by the external environment, controlling the activation of the robots and their synchronization of their activities, perceived and modeled as an adversarial scheduler. We consider a set of adversarial asynchronous schedulers ranging from the classical semi-synchronous (SSYNCH) and fully asynchronous (ASYNCH) settings, including schedulers (emerging when studying the atomicity of the combination of operations in the $\mathit{LCM}$ cycles) whose adversarial power is in between those two. We ask the question: what is the computational relationship between a model $M_1$ under adversarial scheduler $K_1$ ($M_1(K_1)$) and a model $M_2$ under scheduler $K_2$ ($M_2(K_2)$)? For example, are the robots in $M_1(K_1)$ more powerful (i.e., they can solve more problems) than those in $M_2(K_2)$? We answer all these questions by providing, through cross-model analysis, a complete characterization of the computational relationship between the power of the four models of robots under the considered asynchronous schedulers. In this process, we also provide qualified answers to several open questions, including the outstanding one on the proper dominance of SSYNCH over ASYNCH in the case of unrestricted visibility.

We propose a self-stabilizing leader election (SS-LE) protocol on ring networks in the population protocol model. Given a rough knowledge ψ = ⌈log n⌉ + O(1) on the population size n, the proposed protocol lets the population reach a safe configuration within O(n2 log n) steps with high probability starting from any configuration. Thereafter, the population keeps the unique leader forever. Since no protocol solves SS-LE in o(n2) steps with high probability, the convergence time is near-optimal: the gap is only an O(log n) multiplicative factor. This protocol uses only polylog(n) states. There exist two state-of-the-art algorithms in current literature that solve SS-LE on ring networks. The first algorithm uses a polynomial number of states and solves SS-LE in O(n2) steps, whereas the second algorithm requires exponential time but it uses only a constant number of states. Our proposed algorithm provides an excellent middle ground between these two.

Abstract A self-stabilizing distributed algorithm is guaranteed eventually to reach and stay at a legitimate configuration regardless of the initial configuration of a distributed system. In this paper, we propose the generalized dominating set problem, which is a generalization of the dominating set and $k$-redundant dominating set problems. In the generalized dominating set we propose in this paper, each node $P_{i}$ is given its set of domination wish sets, and a generalized dominating set is a set of nodes such that each node is contained in the set or has a wish set in which all its members are in the set. We propose a self-stabilizing distributed algorithm for finding a minimal generalized dominating set in an arbitrary network under the unfair distributed daemon. The proposed algorithm converges in $O(n^{3}m)$ steps and $O(n)$ rounds, where $n$ (resp., $m$) is the number of nodes (resp., edges). Furthermore, it has the safe convergence property with safe convergence time in $O(1)$ rounds. The space complexity of the proposed algorithm is $O(\Delta \log n)$ bits per node, where $\Delta $ is the maximum degree of nodes.

We propose a silent self-stabilizing asynchronous distributed algorithm to find a 2-minimal dominating set (2-MDS) in networks of girth at least 7. Given a graph$G=(V, E)$, a 2-MDS of$G$is a minimal dominating set$D\subseteq V$such that$D\backslash \{p_{i},p_{j}\}\cup\{p_{z}\}$is not a dominating set for any nodes$p_{i},p_{j}\in L (p_{i}\neq p_{j})$and$p_{z}\ /{\!\!\!\in} D$. The girth is the length of the shortest cycles in the graph. We assume that the processes have unique identifiers. The proposed algorithm constructs a 2-MDS in the networks of girth at least 7 under the weakly fair distributed daemon. The time complexity is$O(nH)$rounds, and the space complexity is$O(\log n)$bits per process, where$n$is the number of processes and$H$is the diameter of the network.

An autonomous mobile robot system consisting of many mobile computational entities (called robots) attracts much attention of researchers, and to clarify the relation between the capabilities of robots and solvability of the problems is an emerging issue for a recent couple of decades. Generally, each robot can observe all other robots as long as there are no restrictions for visibility range or obstructions, regardless of the number of robots. In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We call this new computational model defected view model. Under this model, in this paper, we consider the gathering problem that requires all the robots to gather at the same point and propose two algorithms to solve the gathering problem in the adversarial ($N$,$N-2$)-defected model for $N \geq 5$ (where each robot observes at most $N-2$ robots chosen adversarially) and the distance-based (4,2)-defected model (where each robot observes at most 2 closest robots to itself) respectively, where $N$ is the number of robots. Moreover, we present an impossibility result showing that there is no (deterministic) gathering algorithm in the adversarial or distance-based (3,1)-defected model. Moreover, we show an impossibility result for the gathering in a relaxed ($N$, $N-2$)-defected model.

In this paper, we consider the almost uniform deployment problem of mobile agents in dynamic rings, which requires all agents other than one agent to spread uniformly in the ring. In this paper, we consider this problem in 1-interval connected rings, that is, one of the links may be missing at each time step. Focusing on global knowledge given to agents, we clarify the problem solvability and the algorithm performance. First, we consider agents with knowledge of the number n of nodes. Then, we show that the problem can be solved with O(klog⁡n) memory space per agent, O(nlog⁡k) rounds, and a total number of O(kn) moves, where k is the number of agents. Next, we consider agents with knowledge of k. Then, we show that the problem can be solved with O(klog⁡n) memory space per agent, O(n2) rounds, and a total number of O(n2) moves.

In this work, we initiate the study of \emph{smoothed analysis} of population protocols. We consider a population protocol model where an adaptive adversary dictates the interactions between agents, but with probability $p$ every such interaction may change into an interaction between two agents chosen uniformly at random. That is, $p$-fraction of the interactions are random, while $(1-p)$-fraction are adversarial. The aim of our model is to bridge the gap between a uniformly random scheduler (which is too idealistic) and an adversarial scheduler (which is too strict). We focus on the fundamental problem of leader election in population protocols. We show that, for a population of size $n$, the leader election problem can be solved in $O(p^{-2}n \log^3 n)$ steps with high probability, using $O((\log^2 n) \cdot (\log (n/p)))$ states per agent, for \emph{all} values of $p\leq 1$. Although our result does not match the best known running time of $O(n \log n)$ for the uniformly random scheduler ($p=1$), we are able to present a \emph{smooth transition} between a running time of $O(n \cdot \mathrm{polylog} n)$ for $p=1$ and an infinite running time for the adversarial scheduler ($p=0$), where the problem cannot be solved. The key technical contribution of our work is a novel \emph{phase clock} algorithm for our model. This is a key primitive for much-studied fundamental population protocol algorithms (leader election, majority), and we believe it is of independent interest.

We consider the leader election problem in population protocol models. In pragmatic settings of population protocols, self-stabilization is a highly desired feature owing to its fault resilience and the benefit of initialization freedom. However, the design of self-stabilizing leader election is possible only under a strong assumption (i.e. the knowledge of the \emph{exact} size of a network) and rich computational resources (i.e. the number of states). Loose-stabilization, introduced by Sudo et al [Theoretical Computer Science, 2012], is a promising relaxed concept of self-stabilization to address the aforementioned issue. Loose-stabilization guarantees that starting from any configuration, the network will reach a safe configuration where a single leader exists within a short time, and thereafter it will maintain the single leader for a long time, but not forever. The main contribution of the paper is a time-optimal loosely-stabilizing leader election protocol. While the shortest convergence time achieved so far in loosely-stabilizing leader election is $O(\log^3 n)$ parallel time, the proposed protocol with design parameter $τ\ge 1$ attains $O(τ\log n)$ parallel convergence time and $Ω(n^τ)$ parallel holding time (i.e. the length of the period keeping the unique leader), both in expectation. This protocol is time-optimal in the sense of both the convergence and holding times in expectation because any loosely-stabilizing leader election protocol with the same length of the holding time is known to require $Ω(τ\log n)$ parallel time.

In the population protocol model, many problems cannot be solved in a self-stabilizing manner. However, global knowledge, such as the number of nodes in a network, sometimes enables the design of a self-stabilizing protocol for such problems. For example, it is known that we can solve the self-stabilizing leader election in complete graphs if and only if every node knows the exact number of nodes. In this article, we investigate the effect of global knowledge on the possibility of self-stabilizing population protocols in arbitrary graphs. Specifically, we clarify the solvability of the leader election problem, the ranking problem, the degree recognition problem, and the neighbor recognition problem by self-stabilizing population protocols with knowledge of the number of nodes and/or the number of edges in a network.

We propose a self-stabilizing algorithm to construct a minimal weakly ST-reachable directed acyclic graph (DAG), which is suited for routing messages on wireless networks. Given an arbitrary, simple, connected, and undirected graph G = (V, E) and two sets of nodes, senders S(⊂ V) and targets T(⊂ V), a directed subgraph G⃗ of G is a weakly ST-reachable DAG on G, if G⃗ is a DAG and every sender can reach at least one target, and every target is reachable from at least one sender in G⃗. We say that a weakly ST-reachable DAG G⃗ on G is minimal if any proper subgraph of G⃗ is no longer a weakly ST-reachable DAG. This DAG is a relaxed version of the original (or strongly) ST-reachable DAG, where every target is reachable from every sender. This is because a strongly STreachable DAG G does not always exist; some graph has no strongly ST-reachable DAG even in the case |S| = |T | = 2. On the other hand, the proposed algorithm always constructs a weakly ST-reachable DAG for any |S| and |T |. Furthermore, the proposed algorithm is self-stabilizing; even if the constructed DAG deviates from the reachability requirement by a breakdown or exhausting the battery of a node having an arc in the DAG, this algorithm automatically reconstructs the DAG to satisfy the requirement again. The convergence time of the algorithm is O(D) asynchronous rounds, where D is the diameter of a given graph. We conduct small simulations to evaluate the performance of the proposed algorithm. The simulation result indicates that its execution time decreases when the number of sender nodes or target nodes is large.

We propose a self-stabilizing leader election protocol on directed rings in the model of population protocols. Given an upper bound N on the population size n, the proposed protocol elects a unique leader within O(nN) expected steps starting from any configuration and uses O(N) states. This convergence time is optimal if a given upper bound N is asymptotically tight, i.e., N=O(n).

Self-stabilizing and silent distributed algorithms for token distribution in rooted tree networks are given. Initially, each process of a graph holds at most ℓ tokens. Our goal is to distribute the tokens uniformly in the whole network so that every process holds exactly k tokens. In the initial configuration, the total number of tokens in the network may not be nk where n is the number of processes in the network. The root process is given the ability to create a new token or remove a token from the network. We aim to minimize the convergence time, the number of token moves, and the space complexity. First, a self-stabilizing token distribution algorithm that converges within O(nℓ) asynchronous rounds and needs Θ(nhϵ) redundant (or unnecessary) token moves is given, where ϵ=min(k,ℓ−k) and h is the height of the tree network. Next, two novel mechanisms to reduce the number of redundant token moves are presented. One reduces the number of redundant token moves to O(nh) without any additional costs while the other reduces the number of redundant token moves to O(n), but increases the convergence time to O(nhℓ). All given algorithms have constant memory at each process and each link register.

In this article, we present the first leader election protocol in the population protocol model that stabilizes within O(logn) parallel time in expectation with O(logn) states per agent, where n is the number of agents. Given a rough knowledge m of lg n such that m ≥ lg n and m = O(logn), the proposed protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter. This protocol is time-optimal because it was recently proven that any leader election protocol requires Ω(logn) parallel time.

In this paper, we introduce a new graph structure named an ST-reachable directed acyclic graph which is a directed acyclic graph (DAG) that guarantees reachability from every sender to every target (i.e., a directed path exists). When an arbitrary connected undirected graph G=(V,E) and two sets of the vertices, senders S (⊂ V) and targets T (⊂ V), are given, we consider construction of a minimal ST-reachable DAG by changing some undirected edges to arcs and removing the remaining edges. This implies that every node in T is reachable from every node in S on the constructed ST-reachable DAG. In particular, our goals are (1) to find the necessary and sufficient condition that an ST-reachable DAG can be constructed, and (2) to design a self-stabilizing algorithm for constructing a minimal ST-reachable DAG (if exists). In this paper, we present the necessary and sufficient condition that a minimal ST-reachable DAG can be constructed when S ≤ 2 and |T| ≤ 2, and propose a self-stabilizing algorithm to construct an ST-reachable DAG (if exists) when an arbitrary connected undirected graph, S (|S| ≤ 2) and T (|T| ≤ 2) are given. Moreover, our proposed algorithm can detect the non-existence of ST-reachable DAG if there exists no ST-reachable DAG of the given graph and two sets of vertices, S and T.

This paper proposes a new extension of the population protocol (PP) model, the linearly-weighted interaction population protocol (LIPP) model, which introduces weights of agents (or mobile devices) as abstract speeds of agents. The model assumes that the interaction probability between agents is relatively proportional to the weights of the agents, which is almost validated from preliminary simulation results. Each agent can control its weight to adjust its interaction probability. This implies that mobility of agents is semi-passive (not completely passive) since they can change only their abstract speeds. This paper considers how the expected convergence time (measured by the number of interactions) of naive PP protocols for information dissemination, leader election and majority can be improved in the new model by assigning appropriate weighs to agents. The presented results show potential possibility and limitation of the LIPP model.

In this paper, we present a leader election protocol in the population protocol model that stabilizes within O(log n) parallel time in expectation with O(log n) states per agent, where n is the number of agents. Given a rough knowledge m of the population size n such that m ≥ = log2 n and m=O(log n), this protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter.

In the population protocol model [Angluin et al. 2006], it is impossible to design a self-stabilizing leader election protocol without any knowledge of the exact number of nodes in the system. The notion of loose-stabilization, which relaxes the closure requirement of self -stabilization, was introduced in 2009 to circumvent this impossibility. The notion can be described as follows: a loosely-stabilizing protocol guarantees that, starting from any initial configuration, a system reaches a safe configuration eventually, and after that, the system maintains its specification (e.g., the unique leader) not forever, but for a sufficiently long time. The previous work of the authors presented a loosely-stabilizing protocol that solves the leader election on complete graphs using only a given upper bound N on the number of nodes n in the system, instead of the exact value of n. In this paper, we propose two loosely-stabilizing protocols that solve leader election for arbitrary graphs. One is a deterministic protocol that uses the unique identifiers of nodes while the other is a probabilistic protocol that works on anonymous networks. Given an upper bound N on the number of nodes, both protocols maintain a unique leader for Ω(Ne2N) expected steps (holding time) after entering a safe configuration. The first algorithm enters a safe configuration within O(mN log n) expected steps (convergence time) while the second one does this within O(mN2log N) expected steps, where m is the number of edges in the graph. Both protocols require only O(log N) bits for each node's memory. A novel concept, called the same speed timer is introduced, by which all nodes of the system can count down their timers at the same speed. This concept allows to achieve fast convergence time of both algorithms. To design the second protocol, we design a self-stabilizing two-hop coloring protocol, which is interesting in its own right. This protocol uses only O(log N) memory space per node. We establish a lower bound. Any loosely-stabilizing leader election protocol with expected exponential holding time requires Ω(mN) expected convergence time. This lower bound shows a near-optimality of the first algorithm.

Mobile agents (agents) are activities which can move autonomously in a networked system and execute actions at visited nodes. One of the most fundamental problems of agents is exploration, which requires that each node should be visited by at least one agent. For a long time, researchers focus on exploration of static networks. However, exploration of dynamic networks comes to be studied recently. In this paper, we consider exploration of a dynamic torus under some constraints on the dynamics (or topology changes). An n × m torus (3 ≤ n ≤ m) is considered as a collection of n row rings and m column rings. The constraint on the dynamics is that each ring should be 1-interval connected, which allows at most one link to be missing at any time in each ring. On this n × m dynamic torus, we propose exploration algorithms with and without the link presence detection. With the link presence detection, an agent can detect which incident links are missing (if exist) before determining its next move. On the other hand, without the link presence detection, an agent has to determine its next move without knowing which incident links are missing, which makes the agent stay on the same node when the link necessary to the move is missing. We prove for exploration of the n × m dynamic torus that, without the link presence detection, n+1 agents are necessary and sufficient, and, with the link presence detection, ⌈n/2⌉ + 1 agents are necessary and sufficient. Moreover, for both cases, we propose asymptotically optimal algorithms with respect to both the numbers of agents and rounds when n = m.

Self-stabilizing and silent distributed algorithms for token distribution in rooted tree networks are given. Initially, each process of a graph holds at most l tokens. Our goal is to distribute the tokens in the whole network so that every process holds exactly k tokens. In the initial configuration, the total number of tokens in the network may not be equal to nk where n is the number of processes in the network. The root process is given the ability to create a new token or remove a token from the network. We aim to minimize the convergence time, the number of token moves, and the space complexity. A self-stabilizing token distribution algorithm that converges within O(n l) asynchronous rounds and needs Theta(nh epsilon) redundant (or unnecessary) token moves is given, where epsilon = min(k,l-k) and h is the height of the tree network. Two novel ideas to reduce the number of redundant token moves are presented. One reduces the number of redundant token moves to O(nh) without any additional costs while the other reduces the number of redundant token moves to O(n), but increases the convergence time to O(nh l). All algorithms given have constant memory at each process and each link register.

A loosely-stabilizing leader election protocol with polylogarithmic convergence time in the population protocol model is presented in this paper. In the population protocol model, which is a common abstract model of mobile sensor networks, it is known to be impossible to design a self-stabilizing leader election protocol. Thus, in our prior work, we introduced the concept of loose-stabilization, which is weaker than self-stabilization but has similar advantage as self-stabilization in practice. Following this work, several loosely-stabilizing leader election protocols are presented. The loosely-stabilizing leader election guarantees that, starting from an arbitrary configuration, the system reaches a safe configuration with a single leader within a relatively short time, and keeps the unique leader for an sufficiently long time thereafter. The convergence times of all the existing loosely-stabilizing protocols, i.e., the expected time to reach a safe configuration, are polynomial in n where n is the number of nodes (while the holding times to keep the unique leader are exponential in n). In this paper, a loosely-stabilizing protocol with polylogarithmic convergence time is presented. Its holding time is not exponential, but arbitrarily large polynomial in n.

We present a fast loosely-stabilizing leader election protocol in the population protocol model. It elects a unique leader in a poly-logarithmic time and holds the leader for a polynomial time with arbitrarily large degree in terms of parallel time, i.e, the number of steps per the population size.

A novel concept of the same speed timer is presented, and is applied in the population protocol (PP) model to improve the convergence time of existing loosely-stabilizing leader election protocols. Loosely-stabilizing leader election guarantees that, starting from any configuration, the system reaches a safe configuration within a short time (convergence), and after that, the system keeps the unique leader for a long time (closure). Two loosely-stabilizing leader election protocols for arbitrary graphs exist in the literature; one uses identifiers of nodes and the other uses random numbers to elect a unique leader. Both protocols guarantee that the expected convergence time is polynomial and the expected holding time (the time the leader is kept) is exponential. In this paper, convergence time of these protocols is dramatically improved by the same speed timer without impairing the exponential holding time. Specifically, a fast deterministic loosely-stabilizing leader election protocol that uses identifiers of nodes and a fast randomized looselystabilizing leader election protocol are given. The expected convergence time and expected holding time of the former protocol are O(mN log N) and Ω(Ne2N), respectively, where m is the number of edges in the graph and N is a given upper bound on the number of nodes n. The expected convergence time and expected holding time of the latter protocol are O(mN2log n) and Ω(Ne2N), respectively. A self-stabilizing two-hop coloring protocol that uses only O(log n) memory space of each agent is given as a tool of the latter protocol. A lower bound is also given: any loosely-stabilizing leader election protocol with expected exponential holding time requires Ω(mN) expected convergence time.

In the population protocol model Angluin et al. proposed in 2004, there exists no self-stabilizing leader election protocol for complete graphs, arbitrary graphs, trees, lines, degree-bounded graphs and so on unless the protocol knows the exact number of nodes. To circumvent the impossibility, we introduced the concept of loose-stabilization in 2009, which relaxes the closure requirement of self-stabilization. A loosely-stabilizing protocol guarantees that starting from any initial configuration a system reaches a safe configuration, and after that, the system keeps its specification (e.g. the unique leader) not forever, but for a sufficiently long time (e.g. exponentially large time with respect to the number of nodes). Our previous works presented two loosely-stabilizing leader election protocols for arbitrary graphs; One uses agent identifiers and the other uses random numbers to elect a unique leader. In this paper, we present a loosely-stabilizing protocol that solves leader election on arbitrary graphs without agent identifiers nor random numbers. By the combination of virus-propagation and token-circulation, the proposed protocol achieves polynomial convergence time and exponential holding time without such external entities. Specifically, given upper bounds N and Delta of the number of nodes n and the maximum degree of nodes delta respectively, it reaches a safe configuration within O(m*n^3*d + m*N*Delta^2*log(N)) expected steps, and keeps the unique leader for Omega(N*e^N) expected steps where m is the number of edges and d is the diameter of the graph. To measure the time complexity of the protocol, we assume the uniformly random scheduler which is widely used in the field of the population protocols.

Backup servers are effective for maintaining the high availability of cloud services against hardware failures and disasters. For reducing additional costs, the backup servers are shared in the same cloud system. For achieving much more efficient sharing of backup servers to reduce the cost, we focus on the Inter-cloud which enables the sharing of computing resource among multiple cloud systems dynamically. In this paper, we propose a scheme to share backup servers in the Inter-cloud. To evaluate the cost reduction effect of this scheme, we design a model for calculating the optimal number of backup servers and assume several domains of applicability. Based on the calculation results, when each cloud system has 10000 running servers and 100 cloud systems collaborate together for disaster recovery, the proposed scheme can reduce the number of servers for every cloud system from 10000 to 200.

In the future mobile network era and even now, we are faced with more diverse user and social needs for the network. These needs are changing the priorities of necessities on network and also making more practical evaluations indispensable. In general, people take a "shortcut" route when they move from one location to another. However, this will not necessarily be true for future mobile users. A "longcut" route might be highly preferable, depending on their applications that requires longlasting network connectivity or high data rate. Here, the longcut route is the optimal route for maximizing a user's satisfaction, e.g., by considering tradeoffs between the gain in transmission performance and degradation in trip time. This paper proposes a longcut route concept and evaluates its effectiveness in realistic environments by computer simulation using the network simulator ns-2, from the viewpoints of start/goal node locations, the speed of mobile nodes, the number of base stations, and the density of base stations. The results show that even in practical environments the longcut route can provide us with much capacity gain in return for a slightly longer trip time.