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

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

In this paper, we define a new concept neighborhood mutual remainder (NMR). An NMR distributed algorithms should satisfy global fairness, l-exclusion and repeated local rendezvous requirements. We give a simple self-stabilizing algorithm to demonstrate the design paradigm to achieve NMR, and also present applications of NMR to a Look-Compute-Move robot system.

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

Anonymous mobile robots are often classified into synchronous, semi-synchronous, and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. (All patterns formable with memory are formable without memory for synchronous robots, and little is known for asynchronous robots.) However, the gathering problem for two semi-synchronous robots without memory (called oblivious robots in this paper) is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely, static compasses with (possibly incorrect) constant bearings and dynamic compasses the bearings of which can change arbitrarily (immediately before a new look-compute-move cycle starts and after the last cycle ends). For each of the combinations of robot and compass models, we establish the condition on deviation $\phi$ that allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: $\phi < \pi/2$ for semi-synchronous and asynchronous robots with static compasses, $\phi < \pi/4$ for semi-synchronous robots with dynamic compasses, and $\phi < \pi/6$ for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.

Packet filtering provides initial layer of security based upon set of ordered filters called firewall policies. It is a difficult task for the administrator to manage and maintain firewall policies, as it is an error-prone and complicated task for a dynamic network environment. Conflict is a mis-configuration that happens when two or more filters overlap each other, resulting in shadowing and redundancy of the filters. On the other hand, time-based filters are introduced in CISCO firewalls and LINUX iptables to control network traffic on basis of time. It is very handy when a service is required to be available only at certain times of day or even certain days. Conflict occurs in time-based filters when two or more filters falls on same timing. It is required to detect conflicts in time-based filters. We have two main contributions in this paper. First, we propose a mapping mechanism to treat periodic cycles like every day or every specific day of the week, that removes the unnecessary computation. Second, we decompose time into intervals and compute the conflicting filters in each interval. We implemented the mechanism using time divisor comprises of seven primitive time-handling operations. We have also developed a prototype system to prove the effectiveness of the approach. We experimentally analyzed our system with different samples of time-based filters by varying the percentage of periodic cycles and thereby we clarified the effectiveness of the proposed mechanism.

Packet filtering provides initial layer of security based upon set of ordered filters called firewall policies. It examines the network packets and decides whether to accept or deny them. But when a packet matches two or more filters conflicts arise. Due to the conflicts, some filters are never executed and some filters are occasionally executed. It may results into unintended traffic and it is a tedious job for administrator to detect conflicts. Detection of conflicts through geometrical approach provides a systematic and powerful error classification, but as the filters and key fields of header increase, it demands high memory and computation time. To solve this problem, we propose a topological approach called BISCAL (Bit-vector based spatial calculus) to detect the conflicts in the firewall policies. As because of our approach preserves only the topology of the filters, it can reduce memory usage and computation time to a great extend.

We developed an ad hoc on-demand multipath distance vector protocol with path preferential selection probabilities (AODVM-PPSP) for a mobile ad hoc network (MANET). This protocol introduces a new method, in which each node deliberately selects one of the multipath routes to utilize. It adapts preference for the route with the least transmission delay time and node throughput. We examined our protocol under various network loads. We evaluated our protocol with Omnet simulator and the performance is compared with the conventional methods. We found that the multiple routes were efficiently selected and there by resulted in higher packet delivery ratio and lower routing packets. The simulation results show that our proposed protocol has the significant improvement over others.

This paper describes a case study of building a prototype of an immersive three dimensional (3-D) modeler which supports simple two-handed operations. Designing 3-D objects in a virtual environment has a number of advantages for 3-D geometry creation over designing with traditional computer aided design (CAD) tools. In order to enhance the human-computer interaction in a virtual workspace, two-handed spatial input has been incorporated into a few 3-D designing applications. However, existing 3-D designing tools do not utilize two handed interaction for enhancing the interface sufficiently. Our prototype immersive modeler, VLEGO, employs some features of toy blocks to give flexible two-handed interaction for 3-D design. Features of VLEGO can be summarized as follows: Firstly, VLEGO supports various two-handed operations and hence it makes design environment intuitive and efficient. Secondly, possible location and orientation of primitives are discretely limited so that the user can arrange objects accurately with ease. Finally, the system automatically avoids collisions among primitives and adjusts their positions. As a result, precise design of 3-D objects can be achieved easily by using a set of two-handed operations in intuitive way. This paper describes the design and implementation of VLEGO as well as an experiment for examining the effectiveness of two-handed interaction.