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 The domination problem is one of the fundamental graph problems, and there are many variations. In this article, we propose a new problem called the minus ‐domination problem where , and are integers such that , , and . The problem is to assign a value from for each vertex in a graph such that the local summation of values is greater than or equal to . We also propose a framework named the bounded lattice domination for a class of domination problems, including the minus ‐domination problem. Then, we present a self‐stabilizing distributed algorithm under the distance‐2 model for the bounded lattice domination. Here, self‐stabilization is a class of fault‐tolerant distributed algorithms that tolerate transient faults. The time complexity for convergence is , where is the number of processes in a network if the cardinality of the domain of process values is finite and constant. Otherwise, the time complexity for convergence is .

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.

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.

Summary We consider the local (1,|Ni|)‐critical section (CS) problem where Ni is the set of neighboring processes for each process Pi. It dynamically maintains two disjoint dominating sets and is one of the generalizations of the mutual exclusion problem. The problem is one of controlling the system in such a way that, for each process, among its neighbors and itself, at least one process must be in the CS and at least one process must be out of the CS at each time. That is, in the system G=(V,E), there are always two disjoint dominating sets A1(⊂V) and A2(=V\A1) and each process alternates between its rule A1 and A2 infinitely. It is useful for sleep scheduling or cluster head scheduling in sensor networks. In this paper, first, we show the necessary and sufficient conditions to solve the problem without any deadlock detection. To discuss the conditions, we consider an inefficient (costly) self‐stabilizing algorithm for the local (1,|Ni|)‐CS problem. After that, an efficient self‐stabilizing algorithm for the local (1,|Ni|)‐CS problem is proposed under an additional assumption that the graph does not have a special matching, which we call unpreventable colorable maximal matching. The convergence time of the proposed algorithm is O(n) rounds under the weakly fair distributed daemon.

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.

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.

If a graph G = (V, E) has no isolated nodes and D ⊂ V is a minimal dominating set, then V D is a dominating set [1]. In such graphs, there are two disjoint minimal dominating sets A and B. In this paper, we propose an asynchronous self-stabilizing distributed algorithm for finding such a pair of sets with safe convergence. We assume that the first feasible safe configuration satisfies A is a dominating set. The second feasible safe configuration satisfies A is a minimal dominating set. The third feasible safe configuration satisfies A is a minimal dominating set, B is a dominating set and A and B are disjoint. Finally, the legitimate configuration satisfies A and B are disjoint minimal dominating sets.

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

Mutual exclusion is a fundamental process synchronization problem in concurrent systems. In this paper, we propose a unified framework for mutual exclusion, k-mutual exclusion, mutual inclusion, ℓ-mutual inclusion and such, what we call critical section problem. Then, we show that critical section problem is characterized by a pair of integers.

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.

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.

The group mutual exclusion problem is a generalization of mutual exclusion problem such that a set of processes in the same group can enter critical section simultaneously. In this paper, we propose a distributed algorithm for the group mutual exclusion problem in asynchronous message passing distributed systems. Our algorithm is based on tokens, and a process that obtains a token can enter critical section. For reducing message complexity, it uses coterie as a communication structure when a process sends a request messages. Informally, coterie is a set of quorums, each of which is a subset of the process set, and any two quorums share at least one process. The message complexity of our algorithm is O(|Q|) in the worst case, where |Q| is a quorum size that the algorithm adopts. Performance of the proposed algorithm is presented by analysis and discrete event simulation. Especially, the proposed algorithm achieves high concurrency, which is a performance measure for the number of processes that can be in critical section simultaneously.

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. A self-stabilizing system tolerates any kind and any finite number of transient faults, such as message loss, memory corruption, and topology change. Because such transient faults occur so frequently in mobile ad hoc networks, distributed algorithms on them should tolerate such events. In this paper, we propose a self-stabilizing distributed approximation algorithm for the minimum connected dominating set, which can be used, for example, as a virtual backbone or routing in mobile ad hoc networks. The size of the solution by our algorithm is at most 8 |Dopt| + 1, where Dopt is a minimum connected dominating set. The time complexity is O(n2) steps.

A self-stabilizing distributed system is a fault-tolerant distributed system that tolerates any kind and any finite number of transient faults, such as message loss and memory corruption. In this paper, we formulate a concept of safe convergence in the framework of self-stabilization. An ordinary self-stabilizing algorithm has no safety guarantee while it is in converging from any initial configuration. The safe convergence property guarantees that a system quickly converges to a safe configuration, and then, it gracefully moves to an optimal configuration without breaking safety. Then, we propose a minimal independent dominating set algorithm with safe convergence property. Especially, the proposed algorithm computes the lexicographically first minimal independent dominating set according to the process identifier as a priority. The priority scheme can be arbitrarily changed such as stability, battery power and/or computation power of node

A self-stabilizing protocol is a brilliant framework for fault tolerance. It can recover from any number and any type of transient faults and eventually converge to its intended behavior. Performance of a self-stabilizing protocol is usually measured by stabilization time: the time required to complete the convergence to its intended behavior under the assumption that no new fault occurs during the convergence. But a self-stabilizing protocol has no guarantee to complete the convergence if faults are frequently occurred. This paper brings new light to efficiency analysis of stabilization. The efficiency is evaluated with consideration for faults occurring during the convergence. To show the feasibility and effectiveness of the approach, this paper applies the approach to the maximal matching protocol.

Peer-to-peer (P2P) system is an overlay network of peer computers without centralized servers, and many applications have been developed for such networks such as file sharing systems. Because a set of peers dynamically changes, design and verification of efficient protocols is a challenging task. In this paper, we consider an object searching problem under a resource model such that there are some replicas in a system and the lower bound of the ratio /spl rho/=n'/n is known in advance, where n' is a lower bound of the number of peers that hold original or replica for any object type and n is the total number of peers. In addition, we consider object searching with probabilistic success, i.e., for each object search, object must be found with at least probability 0</spl sigma/<1. To solve such a problem efficiently, we propose a new communication structure, named probabilistic weak quorum systems (PWQS), which is an extension of coterie. Then, we propose a fault-tolerant protocol for searching for objects in a P2P system. In our method, each peer does not maintain global information such as the set of all peers and a logical topology with global consistency. In our protocol, each peer communicates only a small part of a peer set and, thus, our protocol is adaptive for huge scale P2P network.

In this paper, we propose a GUI-based learning system for the problem of mutual exclusion in multithreaded programming (MTP) such as race conditions, deadlock and starvation. Threads are group of cooperating program executions with shared memory. A thread in execution is switched one after another, and thread executions are in concurrent. Because mutual exclusion is necessary for avoiding race conditions, understanding the problem of mutual exclusion and its solution is important for students. Deadlock and starvation are bugs of mutual exclusion algorithm such that threads are blocked forever, and threads cannot make progress, respectively. Finding such bugs is difficult because we must check every execution scheduling of threads. To this end, we have been developing a system for learning correct mutual exclusion algorithm in MTP. Our system is designed for university students studying computer science. Proposed system uses a model checking system to detect such bugs by analysis of multithreaded programs written in the MIPS R2000 assembly language. We describe the outline how learners use our system to understand the problem of mutual exclusion in MTP.

Self-stabilization is a theoretical framework of non-masking fault-tolerant algorithms in distributed systems. In this paper, we consider a problem to find fully connected subgraphs (cliques) in a network. In our problem setting, each process P in a network G is given a set of its neighbor processes as input, and must find a set of neighbors that are fully connected together with P. As constraints on solutions which make the problem non-trivial, each process must compute larger cliques as possible, and a process P/sub j/ in a clique that a process P/sub i/ computes must agree on the result, i.e., the same clique must be obtained by P/sub j/. We present a self-stabilizing algorithm to find cliques, and show its correctness and performance.

A self-stabilizing system is a system such that it autonomously converges to a legitimate system state, regardless of the initial system state. The local mutual exclusion problem is the problem of guaranteeing that no two processes neighboring each other execute their critical sections at a time. The process identifiers are said to be chromatic if no two processes neighboring each other have the same identifiers. Under the assumption that the process identifiers are chromatic, this paper proposes two self-stabilizing local mutual exclusion algorithms; one assumes a tree as the topology of communication network and requires 3 states per process, while the other which works on any communication network, requires n + 1 states per process, where n is the number of processes in the system. We also show that the process identifiers being chromatic is close to necessary for a system to have a self-stabilizing local mutual exclusion algorithm. We adopt the shared memory model for communication and the unfair distributed daemon for process scheduling.

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing solution to the problem. Our solution is based on the pruned-MST technique, a heuristic technique to find a minimal cost Steiner tree by pruning unnecessary nodes and edges in a minimum cost spanning tree, provided that a minimum spanning tree is available. Finally we propose an algorithm to reduce the cost of the solution.

A distributed system is said to be self-stabilizing if it will eventually reach a legitimate system state regardless of its initial state. Because of this property, a self-stabilizing system is extremely robust against failures; it tolerates any finite number of transient failures. The ring orientation problem for a ring is the problem of all the processors agreeing on a common ring direction. This paper focuses on the problem of designing a deterministic self-stabilizing ring orientation system with a small number of processor states under the distributed daemon. Because of the impossibility of symmetry breaking, under the distributed daemon, no such systems exist when the number n of processors is even. Provided that n is odd, the best known upper bound on the number of states is 256 in the link-register model, and eight in the state-reading model. We improve the bound down to 6/sup 3/=216 in the link-register model.

A distributed system consists of a set of processes and a set of communication links, each connecting a pair of processes. A distributed system is said to be self-stabilizing if it converges to a correct system state no matter which system state it starts with. A self-stabilizing system is considered to be an ideal fault tolerant system, since it tolerates any kind and any finite number of transient failures. In this paper, we investigate uniform randomized self-stabilizing mutual exclusion systems on unidirectional rings. As far as deterministic systems are concerned, it is well-known that there is no such system when the number 6 of processes (i.e., ring size) is composite, even if a fair central-daemon (c-daemon) is assumed. A fair daemon guarantees that every process will be selected for activation infinitely many times. As for randomized systems, regardless of the ring size, we can design a self-stabilizing system even for a distributed-daemon (d-daemon). However, every system proposed so far assumes a daemon to be fair, and effectively replies on this assumption. This paper tackles the problem of designing a self-stabilizing system, without assuming the fairness of a daemon. As a result, we present a randomized self-stabilizing mutual exclusion system for any size n (including composite size) of a unidirectional ring. The number of process states of the system is 2(n-1).

In 1974, Dijkstra introduced the notion of self-stabilization and presented a token circulation distributed mutual exclusion (DMX) protocol as the first self-stabilizing (SS) algorithm. Since then, many variations of SS DMX algorithms have been presented. Most, if not all, of these algorithms impose stronger assumptions on their execution environments than those provided by common distributed systems. Independently, non SS DMX algorithms have been studied extensively in the last 15 years. This paper presents two SS DMX algorithms that are based on existing non SS DMX algorithms: one is based on a link-locking algorithm and the other is on a node-locking algorithm. Our algorithms assume execution environments that are close to those provided by common distributed systems. Furthermore, they provide better synchronization delays than token circulation SS DMX algorithms. We have implemented our algorithms and tested them with various initial configurations.

The distributed k-mutual-exclusion problem (k-mutex problem) is the problem of guaranteeing that at most k processes at a time can enter a critical section at a time in a distribution system. A method proposed for the solution of the distributed mutual exclusion problem (i.e., 1-mutex problem) by D. Barbara and H. Garcia-Molina (1987) is an extension of majority consensus and uses coteries. The goodness of coterie-based 1-mutex algorithm strongly depends on the availability of coterie, and it has been shown that majority coterie is optimal in this sense, provided that: the network topology is a complete graph, the links never fail, and p, the reliability of the process, is at least 1/2. The concept of a k-coterie, an extension of a coterie, is introduced for solving the k-mutex problem, and lower and upper bounds are derived on the reliability p for k-majority coterie, a natural extension of majority coterie, to be optimal, under conditions (1)-(3). For example, when k=3, p must be greater than 0.994 for k-majority coterie to be optimal.>