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 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.

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$.

ABSTRACT An autonomous mobile robot system is a distributed system consisting of multiple mobile computational entities, called robots, which autonomously and repeatedly perform three fundamental operations: look, compute, and move. Various challenges in such systems, including gathering, pattern formation, and flocking, have been extensively studied to explore the relationship between the robots' capabilities and the feasibility of solving these problems (i.e., solvability). In this study, we focus on the complete visibility problem, which aims to relocate all robots on an infinite grid plane so that every robot is visible to every other robot (i.e., complete visibility). We assume that each robot is a luminous robot (i.e., has a light with a constant number of colors) and opaque (non‐transparent). This paper primarily examines the number of light colors required for each robot to solve the complete visibility problem. Specifically, we investigate the question: “how many colors can we reduce while still achieving complete visibility?” (even under certain stronger assumptions). As an answer to the above question, we show the existence of a deterministic algorithm to achieve complete visibility (i.e., every robot can observe all the other robots) using only two colors of light, if the robots agree on the directions and orientations of both axes. The proposed algorithm correctly works even if robots operate asynchronously and have no knowledge of the total number of robots. Moreover, its spatial complexity (i.e., the area of the smallest enclosed rectangle that includes all robots in the final configuration) ensures the optimal one, , where is the number of robots.

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.

Summary A (σ,τ)‐directed acyclic mixed graph (DAMG) is a mixed graph, which allows both arcs (or directed edges) and (undirected) edges such that there exist exactly σ source nodes and τ sink nodes, but there exists no directed cycle (consisting of only arcs). Each source (resp. sink) node has at least one outgoing (resp. incoming) arc, but no incoming (resp. outgoing) arc. Moreover any other node is neither a source nor a sink node; it has no incident arc or both outgoing and incoming arcs. This article considers maximal (σ,τ)‐DAMG constructions: when an arbitrary undirected connected graph G=(V,E) and two distinct subsets S and T of node set V, where |S|=σ and |T|=τ, are given, construct a maximal (σ,τ)‐DAMG with source node set S and sink node set T by assigning directions to as many edges as possible (ie, by changing edges into arcs). The maximality implies that changing any more edges to arcs violates the conditions of a (σ,τ)‐DAMG (eg, a sink node has an outgoing arc or a directed cycle is created). As a previous work, a self‐stabilizing algorithm for constructing a maximal (1,1)‐DAMG in an arbitrary undirected connected graph is proposed for the case of σ=τ=1. In this article, we consider construction of a maximal (σ,τ)‐DAMG for any σ and τ. First, we introduce a self‐stabilizing algorithm for a maximal (1,2)‐DAMG construction in any connected graph (with few constraints), which is based on the previous work. Concerning generalization of σ and τ to arbitrary values, we first clarify the necessary and sufficient condition under which a (σ,τ)‐DAMG can be constructed in which a source and a sink node sets are given. Then, we propose a generalized self‐stabilizing algorithm that constructs a (σ,τ)‐DAMG when a given graph with a source and a sink node sets satisfies the above condition.

Summary A distributed system consisting of a huge number of computational entities is prone to faults because faults in a few nodes cause the entire system to fail. Consequently, fault tolerance of distributed systems is a critical issue. Checkpoint‐rollback recovery is a universal and representative technique for fault tolerance; it periodically records the entire system state (configuration) to non‐volatile storage, and the system restores itself using the recorded configuration when the system fails. To record a configuration of a distributed system, a specific algorithm known as a snapshot algorithm is required. However, many snapshot algorithms require coordination among all nodes in the system; thus, frequent executions of snapshot algorithms require unacceptable communication cost, especially if the systems are large. As a sophisticated snapshot algorithm, a partial snapshot algorithm has been introduced that takes a partial snapshot (instead of a global snapshot). However, if two or more partial snapshot algorithms are concurrently executed, and their snapshot domains overlap, they should coordinate, so that the partial snapshots (taken by the algorithms) are consistent. In this paper, we propose a new efficient partial snapshot algorithm with the aim of reducing communication for the coordination. In a simulation, we show that the proposed algorithm drastically outperforms the existing partial snapshot algorithm, in terms of message and time complexity.

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.

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 Research to Practice Full Paper presents a distributed pair exercise system for network construction with a dialogue support function. In a certain type of network construction exercise, each of the two learners pairs up and constructs networks. One member of a pair, called driver, operates network components, while another member of the pair, called navigator, checks the driver's work. Several exercise systems realize environments where learners in distant places carry out network construction exercises using virtual machines. However, there are two problems associated with such network construction exercise systems: 1) it is difficult for the members of a pair to edit a common network at the same time and 2) it is difficult for the members of a pair to share attention areas efficiently. Attention areas are areas that a member would like the partner to look at. We propose an exercise system that has GUIs for editing common networks at the same time, selecting attention areas intuitively, and visualizing attention areas. The experiment confirmed that subjects conveyed attention areas more easily, faster, and more accurately using the proposed method than with plain text (traditional method).

Recently, Hadoop attracts much attention of engineers and researchers as an emerging and effective framework for Big Data. HDFS (Hadoop Distributed File System) can manage huge amount of data with high performance and reliability using only commodity hardware. However, HDFS requires a single master node, called a NameNode, to manage the entire namespace of the file system. This causes the SPOF (Single Point Of Failure) problem because the file system becomes inaccessible when the NameNode fails. This also causes a bottleneck of efficiency since all the access requests to the file system have to contact the NameNode. Finally the scale up of a namespace is difficult because the NameNode manages all metadata of the namespace on its own memory, which is limited and expensive resource. In this paper, we propose a new HDFS architecture consisting of several NameNodes to resolve all the above problems.