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.

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

Summary In this work, we study the gathering problem to make multiple agents, who are initially scattered in arbitrary networks, meet at the same node. The network has agents with unique identifiers (IDs), and of them are weakly Byzantine agents that behave arbitrarily, except for falsifying their identifiers. These agents behave in synchronous rounds, and they may start an algorithm at different rounds. Each agent cannot leave information at a node. We propose herein a deterministic algorithm that efficiently achieves gathering with a simultaneous termination having a small number of non‐Byzantine agents. The proposed algorithm concretely works in rounds if the agents know the upper bound on the number of nodes, and at least non‐Byzantine agents exist, where is the length of the largest ID among agents, and is the number of rounds required to explore any network composed of nodes. The literature presents two efficient gathering algorithms with a simultaneous termination. The first algorithm assumes that agents know the number of nodes and achieves the gathering in rounds in the presence of any number of Byzantine agents, where is the length of the largest ID among non‐Byzantine agents. The second algorithm assumes both that agents know and that at least non‐Byzantine agents exist, and it achieves the gathering in rounds. The proposed algorithm is faster than the first existing algorithm and requires fewer non‐Byzantine agents than the second existing algorithm if is given to agents. We propose herein a new technique to simulate a Byzantine consensus algorithm for synchronous message‐passing systems on agent systems to reduce the number of agents.

Summary Fault‐tolerance and self‐organization are critical properties in modern distributed systems. Self‐stabilization is a class of fault‐tolerant distributed algorithms which has the ability to recover from any kind and any finite number of transient faults and topology changes. In this article, we propose a self‐stabilizing distributed algorithm for the 1‐MIS problem under the unfair central daemon assuming the distance‐3 model. Here, in the distance‐3 model, each process can refer to the values of local variables of processes within three hops. Intuitively speaking, the 1‐MIS problem is a variant of the maximal independent set (MIS) problem with improved local optimizations. The time complexity (convergence time) of our algorithm is steps and the space complexity is bits, where is the number of processes. Finally, we extend the notion of 1‐MIS to ‐MIS for each nonnegative integer , and compare the set sizes of ‐MIS () and the maximum independent set.

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.

Summary In this article, we consider the case in which a swarm of robots collaborates in a mission, where a few of the robots behave maliciously. These malicious Byzantine robots may be temporally or constantly controlled by an adversary. The scope is synchronized full information robot operations, where a robot that does not follow the program/policy of the swarm is immediately identified and can be remembered as Byzantine. As robots may be suspected of being Byzantine due to benign temporal malfunctions, it is imperative to forgive and forget, otherwise, a robot cannot assume collaborative actions with any other robot in the swarm. Still, remembering for a while may facilitate a policy of surrounding, isolating and freezing the movement of the misbehaving robots, by several robots, allowing the rest to perform the swarm task with no intervention. We demonstrate the need to periodically forgive and forget to realize swarm several tasks including patrolling/cleaning in the presence of possible Byzantine robots. The policy for achieving the task consists of blocking the movement of the Byzantine robot(s) by some of the robots, while the rest patrol/clean the plane.

Abstract The distributed ledger or blockchain technologies originated from the Bitcoin have been rapidly widespread in recent years. However, it also gives incentive to malicious users who would like to break the system or take advantage of it (steal money, hide some information stored in the ledger, isolate a particular node from the rest of the network, and so forth). Thus, research focusing on overcoming potential attacks to distributed ledgers is required. In this article, we focus on attacks that damage underlying networks of distributed ledgers. Underlying networks offer useful communication primitives such as an atomic broadcast, however, such attacks may degrade the property of the primitives and make distributed ledgers relying on the primitives no longer work. Hence we should design algorithms to make the distributed ledgers still work even when some attacks degrade the primitives. As the first study for such situations, we consider a problem to implement distributed ledgers tolerating the degradation of an underlying atomic broadcast service that distributed ledgers are relying on. We consider the case where the uniform agreement property of the atomic broadcast is degraded, and propose new algorithms that could ensure to reach eventual consistency despite degraded atomic broadcast.

We study the gathering problem to make multiple agents initially scattered in arbitrary networks gather at a single node. There exist k agents with unique identifiers (IDs) in the network, and f of them are weakly Byzantine agents, which behave arbitrarily except for falsifying their IDs. The agents behave in synchronous rounds, and each node does not have any memory like a whiteboard. In the literature, there exists a gathering algorithm that tolerates any number of Byzantine agents, while the fastest gathering algorithm requires Ω( f 2) non-Byzantine agents.

We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other but are endowed with visibility sensors that allow them to see the positions of the other robots. Most investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configurations. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robot unless it is their current node. Consequently, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network.

In this paper, we focus on graph class identification problems in the population protocol model. A graph class identification problem aims to decide whether a given communication graph is in the desired class (e.g. whether the given communication graph is a ring graph). Angluin et al. proposed graph class identification protocols with directed graphs and designated initial states under global fairness [Angluin et al., DCOSS2005]. We consider graph class identification problems for undirected graphs on various assumptions such as initial states of agents, fairness of the execution, and initial knowledge of agents. In particular, we focus on lines, rings, $k$-regular graphs, stars, trees, and bipartite graphs. With designated initial states, we propose graph class identification protocols for $k$-regular graphs, and trees under global fairness, and propose a graph class identification protocol for stars under weak fairness. Moreover, we show that, even if agents know the number of agents $n$, there is no graph class identification protocol for lines, rings, $k$-regular graphs, trees, or bipartite graphs under weak fairness. On the other hand, with arbitrary initial states, we show that there is no graph class identification protocol for lines, rings, $k$-regular graphs, stars, trees, or bipartite graphs.

In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of arbitrary communication graphs. As a result, we investigate the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight.

In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of \emph{arbitrary} communication graphs. As a result, we clarify the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight.

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.

We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: $M_{init}$, which denotes the number of nodes between two border nodes, and $O_{init}$, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{init}$ or $O_{init}$ is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.

We focus on a uniform partition problem in a population protocol model. The uniform partition problem aims to divide a population into k groups of the same size, where k is a given positive integer. In the case of k=2 (called uniform bipartition), a previous work clarified space complexity under various assumptions: 1) an initialized base station (BS) or no BS, 2) weak or global fairness, 3) designated or arbitrary initial states of agents, and 4) symmetric or asymmetric protocols, except for the setting that agents execute a protocol from arbitrary initial states under weak fairness in the model with an initialized base station. In this paper, we clarify the space complexity for this remaining setting. In this setting, we prove that P states are necessary and sufficient to realize asymmetric protocols, and that P+1 states are necessary and sufficient to realize symmetric protocols, where P is the known upper bound of the number of agents. From these results and the previous work, we have clarified the solvability of the uniform bipartition for each combination of assumptions. Additionally, we newly consider an assumption on a model of a non-initialized BS and clarify solvability and space complexity in the assumption. Moreover, the results in this paper can be applied to the case that k is an arbitrary integer (called uniform k-partition).

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

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.

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.

In this paper, we consider the uniform deployment problem of mobile agents in asynchronous unidirectional rings, which requires the agents to uniformly spread in the ring. The uniform deployment problem is in striking contrast to the rendezvous problem which requires the agents to meet at the same node. While rendezvous aims to break the symmetry, uniform deployment aims to attain the symmetry. It is well known that the symmetry breaking is difficult in distributed systems and the rendezvous problem cannot be solved from some initial configurations . Hence, we are interested in clarifying what difference the uniform deployment problem has on the solvability and the number of agent moves compared to the rendezvous problem. We consider two problem settings, with knowledge of k (or n ) and without knowledge of k or n where k is the number of agents and n is the number of nodes. First, we consider agents with knowledge of k (or n since k and n can be easily obtained if one of them is given). In this case, we propose two algorithms. The first algorithm solves the uniform deployment problem with termination detection. This algorithm requires O ( k log n ) memory space per agent, O ( n ) time, and O ( k n ) total moves. The second algorithm also solves the uniform deployment problem with termination detection. This algorithm reduces the memory space per agent to O ( log n ) , but uses O ( n log k ) time, and requires O ( k n ) total moves. Both algorithms are asymptotically optimal in terms of total moves since there are some initial configurations such that agents require Ω ( k n ) total moves to solve the problem. Next, we consider agents with no knowledge of k or n . In this case, we show that, when termination detection is required, there exists no algorithm to solve the uniform deployment problem. For this reason, we consider the relaxed uniform deployment problem that does not require termination detection, and we propose an algorithm to solve the relaxed uniform deployment problem. This algorithm requires O ( ( k ∕ l ) log ( n ∕ l ) ) memory space per agent, O ( n ∕ l ) time, and O ( k n ∕ l ) total moves when the initial configuration has symmetry degree l . This means that the algorithm can solve the problem more efficiently when the initial configuration has higher symmetric degree (i.e., is closer to uniform deployment). Note that all the proposed algorithms achieve uniform deployment from any initial configuration, which is a striking difference from the rendezvous problem because the rendezvous problem is not solvable from some initial configurations .

In this paper, we consider the partial gathering problem of mobile agents in asynchronous tree networks. The partial gathering problem is a generalization of the classical gathering problem, which requires that all the agents meet at the same node. The partial gathering problem requires, for a given positive integer g, that each agent should move to a node and terminate so that at least g agents should meet at each of the nodes they terminate at. The requirement for the partial gathering problem is weaker than that for the (well-investigated) classical gathering problem, and thus, we clarify the difference on the move complexity between them. We consider two multiplicity detection models: weak multiplicity detection and strong multiplicity detection models. In the weak multiplicity detection model, each agent can detect whether another agent exists at the current node or not but cannot count the exact number of the agents. In the strong multiplicity detection model, each agent can count the number of agents at the current node. In addition, we consider two token models: non-token model and removable token model. In the non-token model, agents cannot mark the nodes or the edges in any way. In the removable-token model, each agent initially leaves a token on its initial node, and agents can remove the tokens. Our contribution is as follows. First, we show that for the non-token model agents require Ω(kn) total moves to solve the partial gathering problem, where n is the number of nodes and k is the number of agents. Second, we consider the weak multiplicity detection and non-token model. In this model, for asymmetric trees, by a previous result agents can achieve the partial gathering in O(kn) total moves, which is asymptotically optimal in terms of total moves. In addition, for symmetric trees we show that there exist no algorithms to solve the partial gathering problem. Third, we consider the strong multiplicity detection and non-token model. In this model, for any trees we propose an algorithm to achieve the partial gathering in O(kn) total moves, which is asymptotically optimal in terms of total moves. At last, we consider the weak multiplicity detection and removable-token model. In this model, we propose an algorithm to achieve the partial gathering in O(gn) total moves. Note that in this model, agents require Ω(gn) total moves to solve the partial gathering problem. Hence, the second proposed algorithm is also asymptotically optimal in terms of total moves.

In this paper, we consider a uniform bipartition problem in a population protocol model. The goal of the uniform bipartition problem is to divide a population into two groups of the same size. We study the problem under various assumptions: 1) a population with or without a base station, 2) weak or global fairness, 3) symmetric or asymmetric protocols, and 4) designated or arbitrary initial states. As a result, we completely clarify constant-space solvability of the uniform bipartition problem and, if solvable, propose space-optimal protocols.

We present a new self-stabilizing 1-maximal matching algorithm that works under the distributed unfair daemon for arbitrarily shaped networks. Our algorithm is efficient (its stabilization time is O(e) moves, where e denotes the number of edges in the network). Besides, our algorithm is optimal with respect to identifiers locality (we assume node identifiers are distinct up to distance three, a necessary condition to withstand arbitrary networks).

In this paper, we consider the uniform deployment problem of mobile agents in asynchronous unidirectional rings, which requires the agents to uniformly spread in the ring. The uniform deployment problem is striking contrast to the rendezvous problem which requires the agents to meet at the same node. While the rendezvous aims to break the symmetry, the uniform deployment aims to attain the symmetry. Hence, we are interested in clarifying how easily the uniform deployment problem can be solved compared to the rendezvous problem. We consider two problem settings. First, we consider agents with knowledge of k, where k is the number of agents. In this case, our proposed algorithm solves the uniform deployment problem with termination detection. This algorithm requires O(log n) memory per agent, O(n log k) time, and O(kn) total moves, where n is the number of nodes. Next, we consider agents with no knowledge of k or n. In this case, we show that, when termination detection is required, there exists no algorithm to solve the uniform deployment problem. For this reason, we consider the relaxed uniform deployment problem that does not require termination detection, and we propose an algorithm to solve the relaxed uniform deployment problem. This algorithm requires O(k/l log (n/l)) memory per agent, O(n/l) time, and O(kn/l) total moves, where l is the symmetry degree of the initial configuration (l ≥ 1). Note that both the algorithms achieve the uniform deployment from any initial configuration, which is a striking difference from the rendezvous problem because the rendezvous problem is not solvable from some initial configurations.

In this paper, we consider the partial gathering problem of mobile agents in asynchronous unidirectional rings equipped with whiteboards on nodes. The partial gathering problem is a new generalization of the total gathering problem. The partial gathering problem requires, for a given integer g, that each agent should move to a node and terminate so that at least g agents should meet at the same node. The requirement for the partial gathering problem is weaker than that for the (well-investigated) total gathering problem, and thus, we have interests in clarifying the difference on the move complexity between them. We propose three algorithms to solve the partial gathering problem. The first algorithm is deterministic but requires unique ID of each agent. This algorithm achieves the partial gathering in O(gn) total moves, where n is the number of nodes. The second algorithm is randomized and requires no unique ID of each agent (i.e., anonymous). This algorithm achieves the partial gathering in expected O(gn) total moves. The third algorithm is deterministic and requires no unique ID of each agent. For this case, we show that there exist initial configurations in which no algorithm can solve the problem and agents can achieve the partial gathering in O(kn) total moves for solvable initial configurations, where k is the number of agents. Note that the total gathering problem requires Ω(kn) total moves, while the partial gathering problem requires Ω(gn) total moves in each model. Hence, we show that the move complexity of the first and second algorithms is asymptotically optimal.

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.

We consider the gathering problem of multiple (mobile) agents in anonymous unidirectional ring networks under the constraint that each agent knows neither the number of nodes nor the number of agents. For this problem, we fully characterize the relation between probabilistic solvability and termination detection. First, we prove for any (small) constant p(0 <; p ≤ 1) that no randomized algorithm exists that solves, with probability p, the gathering problem with (termination) detection. For this reason, we consider the relaxed gathering problem, called the gathering problem without detection, which does not require termination detection. We propose a randomized algorithm that solves, with any given constant probability p(0 <; p <; 1), the gathering problem without detection. Finally, we prove that no randomized algorithm exists that solves, with probability 1, the gathering problem without detection.

In this paper, we present a local-information-based self-optimizing routing protocol Zigzag in virtual grid networks. A virtual grid network is obtained by virtually dividing a wireless network into a grid of geographical square regions called cells, and is used in MANETs and sensor networks to reduce energy consumption. A single node is selected as a router at each cell and inter-cell communication is realized by using the routers. Other nodes in the cell have no responsibility for inter-cell communication and can become inactive to save energy consumption. We consider maintenance of an inter-cell communication path to a destination node from its source node. When the destination node moves to a cell next to the current one, the path can be simply updated by extending it to the next cell. But, if the destination node moves around the network, the path becomes redundantly long and needs to be shortened. In this paper, we propose a self-optimizing routing protocol Zigzag in virtual grid networks, which can transform any given inter-cell path to a shortest (or minimum-hop) one by repeatedly applying local updates on the path. The routers locally and asynchronously update the path based only on local information and require no global information of the path such as the locations of the destination and the source nodes. We also show that the convergence time to a shortest path from any given path P is O(|P|) in the synchronous execution where |P| is the length (or the number of hops) of P.

We consider the problem of gathering n anonymous and oblivious mobile robots, which requires that all robots meet in finite time at a nonpredefined point. While the gathering problem cannot be solved deterministically without assuming any additional capabilities for the robots, randomized approaches easily allow it to be solvable. However, the randomized solutions currently known have a time complexity that is exponential in n with no additional assumption. This fact yields the following two questions: Is it possible to construct a randomized gathering algorithm with polynomial expected time? If it is not possible, what is the minimal additional assumption necessary to obtain such an algorithm? In this paper, we address these questions from the aspect of multiplicity-detection capabilities. We newly introduce two weaker variants of multiplicity detection, called local-strong and local-weak multiplicity, and investigate whether those capabilities permit a gathering algorithm with polynomial expected time or not. The contribution of this paper is to show that any algorithm only assuming local-weak multiplicity detection takes exponential number of rounds in expectation. On the other hand, we can obtain a constant-round gathering algorithm using local-strong multiplicity detection. These results imply that the two models of multiplicity detection are significantly different in terms of their computational power. Interestingly, these differences disappear if we take one more assumption that all robots are scattered (i.e., no two robots stay at the same location) initially. We can obtain a gathering algorithm that takes a constant number of rounds in expectation, assuming local-weak multiplicity detection and scattered initial configurations.

This paper introduces a smart office chair, Owens Luis, whose pronunciation has a meaning of “an encouraging chair (****)” in Japanese. For most of the people, office environments are the place where they spend the longest time while awake. To improve the quality of life (QoL) in the office, Owens Luis monitors an office worker's mental and physiological states such as sleepiness and concentration, and controls the working environment by multi-modal displays including a motion chair, a variable color-temperature LED light and a hypersonic directional speaker.

We propose a smart office system that recognizes office workers' mental and physiological states to improve their quality of life at office. We integrated our systems into a single smart office environment. In this article we show the implementation of the smart office system and the details of each of its components such as I/O devices.

We consider the parallel computing environment where m organizations provide machines and several jobs to be executed. While cooperation of organizations is required to minimize the global makespan, each organization also expects the faster completion of its own jobs primarily and thus it is not necessarily cooperative. To handle the situations, we formulate the ¿-cooperative multi-organization scheduling problem (¿-MOSP), where ¿ ¿ 1 is a parameter representing the degree of cooperativeness. ¿-MOSP minimizes the makespan under the cooperation constraint that each organization does not allow the completion time of its own jobs to be delayed ¿ times of that in the case where those jobs are executed by itself. In this paper, we aim to reveal the relation between the makespan and the degree of cooperativeness. First, we investigate the relation between ¿ and the quality of the global makespan. For ¿ = 1 (i.e., each organization never sacrifices its completion time), we show an instance where the cooperation constraint degrades the optimal makespan by m times. In contrast, for ¿ > 1, we can construct an algorithm transforming any unconstrained schedule to one satisfying the cooperation constraint. This algorithm bounds the degradation ratio by ¿/(¿ - 1), which implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of ¿-MOSP. We show its strongly NPhardness and inapproximability for the approximation factor less than max{(¿ + l)/¿, 3/2}. We also show the hardness of transformation: Even if an optimal schedule under no cooperation constraint is given, no polynomial-time algorithm finds an optimal schedule for ¿-MOSP. This result is a witness for inexistence of general polynomial-time transformation algorithms that preserve the approximation ratio.