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 The f-fault-tolerant connectivity labeling (f-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connectivity of two vertices s and t under the presence of at most f faulty edges only from the labels of s, t, and the faulty edges. This paper presents a new deterministic f-FTC labeling scheme attaining $$O(f^2 \textrm{polylog}(n))$$ O ( f 2 polylog ( n ) ) -bit label size and a polynomial construction time, which settles the open problem left by Dory and Parter (in: Proceedings of the 2021 ACM symposium on principles of distributed computing (PODC), pp 445–455, 2021). The key ingredient of our construction is to develop a deterministic counterpart of the graph sketch technique by Ahn et al. (in: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems (PODS), pp 5–14, 2012), via some natural connection with the theory of error-correcting codes. This technique removes one major obstacle in de-randomizing the Dory–Parter scheme. The whole scheme is obtained by combining this technique with a new deterministic graph sparsification algorithm derived from the seminal $$\epsilon $$ ϵ -net theory, which is also of independent interest. As byproducts, our result deduces the first deterministic fault-tolerant approximate distance labeling scheme with a non-trivial performance guarantee and an improved deterministic fault-tolerant compact routing. The authors believe that our new technique is potentially useful in the future exploration of more efficient FTC labeling schemes and other related applications based on graph sketches.

An \emph{$α$-approximate vertex fault-tolerant distance sensitivity oracle} (\emph{$α$-VSDO}) for a weighted input graph $G=(V, E, w)$ and a source vertex $s \in V$ is the data structure answering an $α$-approximate distance from $s$ to $t$ in $G-x$ for any given query $(x, t) \in V \times V$. It is a data structure version of the so-called single-source replacement path problem (SSRP). In this paper, we present a new \emph{nearly linear-time} algorithm of constructing a $(1 + ε)$-VSDO for any directed input graph with polynomially bounded integer edge weights. More precisely, the presented oracle attains $\tilde{O}(m \log (nW)/ ε+ n \log^2 (nW)/ε^2)$ construction time, $\tilde{O}(n \log (nW) / ε)$ size, and $\tilde{O}(1/ε)$ query time, where $n$ is the number of vertices, $m$ is the number of edges, and $W$ is the maximum edge weight. These bounds are all optimal up to polylogarithmic factors. To the best of our knowledge, this is the first non-trivial algorithm for SSRP/VSDO beating $\tilde{O}(mn)$ computation time for directed graphs with general edge weight functions, and also the first nearly linear-time construction breaking approximation factor 3. Such a construction has been unknown even for undirected and unweighted graphs. In addition, our result implies that the known conditional lower bounds for the exact SSRP computation does not apply to the case of approximation.

We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of connected acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy.

The f-fault-tolerant connectivity labeling (f-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connectivity of two vertices s and t under the presence of at most f faulty edges only from the labels of s, t, and the faulty edges. This paper presents a new deterministic f-FTC labeling scheme attaining O(f2 polylog(n))-bit label size and a polynomial construction time, which settles the open problem left by Dory and Parter [18]. The key ingredient of our construction is to develop a deterministic counterpart of the graph sketch technique by Ahn, Guha, and McGreger [4], via some natural connection with the theory of error-correcting codes. This technique removes one major obstacle in de-randomizing the Dory-Parter scheme. The whole scheme is obtained by combining this technique with a new deterministic graph sparsification algorithm derived from the seminal ϵ-net theory, which is also of independent interest. As byproducts, our result deduces the first deterministic fault-tolerant approximate distance labeling scheme with a non-trivial performance guarantee and an improved deterministic fault-tolerant compact routing. The authors believe that our new technique is potentially useful in the future exploration of more efficient FTC labeling schemes and other related applications based on graph sketches.

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

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

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.

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

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

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

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

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

This paper presents a randomized self-stabilizing algorithm that elects a leader $r$ in a general $n$-node undirected graph and constructs a spanning tree $T$ rooted at $r$. The algorithm works under the synchronous message passing network model, assuming that the nodes know a linear upper bound on $n$ and that each edge has a unique ID known to both its endpoints (or, alternatively, assuming the $KT_{1}$ model). The highlight of this algorithm is its superior communication efficiency: It is guaranteed to send a total of $\tilde{O} (n)$ messages, each of constant size, till stabilization, while stabilizing in $\tilde{O} (n)$ rounds, in expectation and with high probability. After stabilization, the algorithm sends at most one constant size message per round while communicating only over the ($n - 1$) edges of $T$. In all these aspects, the communication overhead of the new algorithm is far smaller than that of the existing (mostly deterministic) self-stabilizing leader election algorithms. The algorithm is relatively simple and relies mostly on known modules that are common in the fault free leader election literature; these modules are enhanced in various subtle ways in order to assemble them into a communication efficient self-stabilizing algorithm.

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

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

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

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

Temporal graphs (or evolving graphs) are time-varying graphs where time is assumed to be discrete. In this paper, we consider for the first time the problem of exploring temporal graphs of arbitrary unknown topology. We study the feasibility of exploration, under both the Fsync and Ssync schedulers, focusing on the number of agents necessary and sufficient to explore such graphs. We first consider the minimal (i.e., less restrictive) assumption on the dynamics of the graph under which exploration is still feasible: temporal connectivity. Let ℋ be the class of temporally connected graphs; we show that for any temporal graph ? ∈ ℋ the number of agents sufficient to perform exploration is related to the number of its transient edges, a parameter η(?) we call evanescence of the graph. More precisely, any ? ∈ ℋ can be explored by a team of k ≥ 2 η(?) +1 agents; this bound is tight as we prove there are ? ∈ ℋ that cannot be explored by 2 η(?) agents. We then turn our attention to the well-known stronger assumption on the dynamics of the graph, called 1-interval connectivity: the graph is connected at any time step. Let ? ⊂ ℋ be the class of these always-connected temporal graphs. For this class, we prove the existence of a difference between Fsync and Ssync when there is a bound ? on the number of edges missing at each time. In fact, we show a tight bound of 2 ? +1 on the number of agents necessary and sufficient in Ssync, and a smaller tight bound of 2 ? in Fsync. As a corollary, we re-establish two recently published bounds for 1-interval connected rings.

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

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

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

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

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

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

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.

We consider the problem of aggregating data in a dynamic graph, that is, aggregating the data that originates from all nodes in the graph to a specific node, the sink. In our model, nodes are endowed with unlimited memory and unlimited computational power. Yet, we assume that communications between nodes are carried out with pairwise interactions, where nodes can exchange control information before deciding whether they transmit their data or not, given that each node is allowed to transmit its data at most once. When a node receives a data from a neighbor, the node may aggregate it with its own data. We are interested in giving lower bounds for this problem, under two possible adversaries: the oblivious adversary, and the randomized adversary that chooses the pairwise interactions uniformly at random. For the online adaptive and the oblivious adversary, we give impossibility results when nodes have no knowledge about the graph and are not aware of the future. For the randomized adversary, we propose two optimal algorithms, (i) when nodes have no knowledge at all and (ii) when each node knows its future pairwise interactions with the sink.

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

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

We give a silent self-stabilizing protocol for computing a maximum matching in an anonymous network with a tree topology. The round complexity of our protocol is O(diam), where diam is the diameter of the network, and the step complexity is O(n*diam), where n is the number of processes in the network. The working space complexity is O(1) per process, although the output necessarily takes O(log(delta)) space per process, where delta is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group Z_7.

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.

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

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.

The energy is a critical resource in Wireless Sensor Networks that impacts on networks lifetime. In this paper, we propose a distributed self-stabilizing algorithm of topology control to preserve energy in case of communications by broadcast. The topology control is achieved by the reduction of the transmission power of the nodes in the network. The self-stabilizing property is a very desirable property in Wireless Sensor Networks that guarantees to reach a correct behavior in a finite number of steps, regardless of its initial state. Our solution is validated by extensive simulations. The obtained results show the efficiency of our solution in case of communication by broadcast.

Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permit to cope with arbitrary malicious behaviors. Combining these two properties proved difficult: it is impossible to contain the spatial impact of Byzantine nodes in a self-stabilizing context for global tasks such as tree orientation and tree construction. We present and illustrate a new concept of Byzantine containment in stabilization. Our property, called Strong Stabilization enables to contain the impact of Byzantine nodes if they actually perform too many Byzantine actions. We derive impossibility results for strong stabilization and present strongly stabilizing protocols for tree orientation and tree construction that are optimal with respect to the number of Byzantine nodes that can be tolerated in a self-stabilizing context.

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

This paper demonstrates the usefulness of distributed local verification of proofs, as a tool for the design of algorithms. In particular, it introduces a somewhat generalized notion of distributed local proofs, and utilizes it for improving the memory size complexity, while obtaining time efficiency too.

A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external intervention in finite time. In this paper, we consider the problem of constructing self-stabilizingly a locally maximizable task (such as constructing a maximal independent set, a maximal matching, or a grundy coloring) in uniform unidirectional networks of arbitrary shape. On the negative side, we present evidence that in uniform networks, deterministic self-stabilization of this problem is impossible. Also, the silence property (i.e. having communication fixed from some point in every execution) is impossible to guarantee, either for deterministic or for probabilistic variants of protocols. On the positive side, we present a series of generic protocols that can be instantiated for all considered locally maximizable tasks. First, we design a deterministic protocol for arbitrary unidirectional networks with unique identifiers that exhibits polynomial space and time complexity in asynchronous scheduling. We complement the study with probabilistic protocols for the uniform case: the first probabilistic protocol requires infinite memory but copes with asynchronous scheduling, while the second probabilistic protocol has polynomial space complexity but can only handle synchronous scheduling. Both probabilistic solutions have expected polynomial time complexity.

In this paper, our focus is to lower the communication complexity of self-stabilizing protocols below the need of checking every neighbor forever. Our contribution is threefold: (i) We provide new complexity measures for communication efficiency of self-stabilizing protocols, especially in the stabilized phase or when there are no faults, (ii) On the negative side, we show that for non-trivial problems such as coloring, maximal matching, and maximal independent set, it is impossible to get (deterministic or probabilistic) self-stabilizing solutions where every participant communicates with less than every neighbor in the stabilized phase, and (iii) On the positive side, we present protocols for maximal matching and maximal independent set such that a fraction of the participants communicates with exactly one neighbor in the stabilized phase.

Topology embedding enables us to execute a protocol designed for a specific (virtual) topology on another(real) topology by embedding the virtual topology on the real topology. In this paper, we propose a self-stabilizing emulation technique that provides reliable communication on a virtual topology in the presence of transient faults. The proposed protocol improves the execution slowdown of previous protocols and provides adaptive message delivery delay on the emulated channels, which is a new type of adaptability against transient faults.

Reliable and fault-tolerant distributed systems have been attracting more and more attention (see Autonomic Computing Project by IBM, http://www-03.ibm.com/autonomic/). A self-stabilizing protocol is a fault-tolerant protocol that guarantees autonomous recovery from any number of and any type of faults that can affect the data stored locally at some process(es). If the impact of the faults can be contained to the affected process(es) and some of its immediate neighbors, then the protocol is also fault-containing. We present a new method, called causal simulation, which preserves the fault-containing property of ring protocols executed on trees.

In this article, we quantify the amount of “practical” information (i.e., views obtained from the neighbors, colors attributed to the nodes and links) to obtain “theoretical” information (i.e., the local topology of the network up to distance k ) in anonymous networks. In more detail, we show that a coloring at distance 2 k + 1 is necessary and sufficient to obtain the local topology at distance k that includes outgoing links. This bound drops to 2 k when outgoing links are not needed. A second contribution of this article deals with color bootstrapping (from which local topology can be obtained using the aforementioned mechanisms). On the negative side, we show that ( i ) with a distributed daemon, it is impossible to achieve deterministic color bootstrap, even if the whole network topology can be instantaneously obtained, and ( ii ) with a central daemon, it is impossible to achieve distance m when instantaneous topology knowledge is limited to m − 1. On the positive side, we show that ( i ) under the k -central daemon, deterministic self-stabilizing bootstrap of colors up to distance k is possible provided that k -local topology can be instantaneously obtained, and ( ii ) under the distributed daemon, probabilistic self-stabilizing bootstrap is possible for any range.

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.

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.

The condition-based approach is one of the sophisticated methods used to overcome several impossibility results in the distributed consensus problem (e.g., impossibility of fault tolerance in asynchronous consensus or time complexity lower bounds in synchronous consensus). It introduces conditions on input vectors to specify subsets of all possible input vectors to consensus algorithms and condition-based algorithms can circumvent the impossibility if actual input vectors satisfy a particular condition. In this paper, we present a new condition-based paradigm for synchronous consensus. We introduce the new concept of adaptation on the time complexity of condition-based algorithms and present the adaptive condition-based approach to synchronous consensus. In our approach, all possible input vectors are classified into hierarchical conditions according to their difficulty called the legality level. The execution time of adaptive condition-based algorithms depends on the legality level of input vectors. We propose two adaptive condition-based algorithms for synchronous consensus. The first algorithm requires that the majority of processes be correct, and terminates within min{f+2, t+1} l rounds if lf holds.

/spl Delta/-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: The correct process terminates its execution within a constant time /spl Delta/ (/spl Delta/-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the /spl Delta/-timed uniform consensus problem in presence of f/sub t/ crash processes and f/sub c/ timing-faulty processes. This paper proposes a /spl Delta/-timed uniform consensus algorithms. The proposed algorithm is adaptive in the following sense: It solves the /spl Delta/-timed uniform consensus when at least f/sub t/ + 1 correct processes exist in the system. If the system has less than f/sub t/ + 1 correct processes, the algorithm cannot solve the /spl Delta/-timed uniform consensus. However, as long as f/sub t/ + 1 processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any /spl Delta/-timed uniform consensus algorithm tolerating up to f/sub t/ timing-faulty processes requires that the system has at least f/sub t/ + 1 correct processes. This impossibility result implies that the proposed algorithm attains the maximal resilience about the number of faulty processes. We also show that any /spl Delta/-timed uniform consensus algorithm tolerating up to f/sub t/ timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than f/sub t/ + 1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.

Self-stabilization is a promising paradigm for achieving fault-tolerance of distributed systems. A self-stabilizing protocol can converge to its intended behavior even when it starts from any system configuration, and, thus, can tolerate any type and any number of transient faults. The PIF (propagation of information with feedback) scheme in a tree network allows the root process to broadcast its information to all other processes and to collect their responses. Many distributed systems utilize the PIF scheme as a fundamental communication scheme. This paper first formalizes the pipelined PIF in tree networks, and proposes a self-stabilizing protocol for the pipelined PIF. The protocol applies the PIF to a sequence of information in a pipelined fashion. The protocol has stabilizing time of O(h) (where h is the height of the tree network). After stabilization, it completes each PIF in O(h) asynchronous rounds and has throughput of O(1). Moreover, the protocol achieves fault-containment: for a complete binary tree network, its expected stabilizing time from 1-faulty configurations is O(1).

This paper presents a new BIST (Built-In Self-Test) method for register transfer level data paths based on both hierarchical testing and a "test-per-clock" scheme. In the proposed method, test pattern generators and response analyzers are placed on primary inputs and primary outputs, and test patterns and test responses are transferred along paths in the data paths. This paper proposes a new testability for BIST, concurrent single-control testability, and presents a new BIST method based on the testability. The concurrent single-control testability is an extension of a previous single-control testability and has advantage that test application time becomes shorter because multiple combinational modules can be tested at the same time (i.e., concurrent testing). Our experimental results show that the proposed method reduces test application time without increasing so much hardware overhead compared with the previous method.

The ability of a system to recover from unexpected change in its environment or disruptions to its internal state is an indication of robust design and autonomous control. Recovery can be constrained by service availability requirements, so that even during periods of recovery, new service requests should be admitted and processed in a timely manner. Given that complex systems are constructed from many components, it is sensible to investigate how individual components can facilitate recovery and also satisfy availability requirements. The component presented is a search tree data structure that can recover from any disruption: it is a self-stabilizing data structure. No matter how severe the damage to its internal state, new operations on the data structure behave properly and the responses to operations are accurate indicators of any change to the search tree, even as the search tree recovery is underway. This paper resolves, for the first time, issues of dynamic allocation and pointer organization in a stabilizing data structure. After any sequence of O(m) operations in an arbitrary initial search tree of m nodes, the tree becomes balanced, all operations have O(lg n) running time, and free chains are adequate to supply new nodes for insertions. To meet availability constraints, operations have O(lg K) running time during periods of recovery, where K is the maximum number of items that the data structure can contain.

Abstract — This paper presents a non-scan design-fortestability (DFT) method for VLSIs designed at registertransfer level (RTL) to achieve complete fault efficiency. In RTL design, a VLSI generally consists of a controller and a data path. The controller and the data path are connected with internal signals: control signals and status signals. The proposed method consists of the following two steps. First, we apply our DFT methods [1] and [2, 3] to the controller and the data path, respectively. Then, to support at-speed testing, we append a test plan generator which generates a sequence of test control vectors for the modified data path. Our experimental results show that the proposed method can reduce significantly both of test generation time and test application time compared with the full-scan design, though the hardware overhead of our method is slightly larger than that of the full-scan design. I.

In this paper, we introduce strong self-testability for data paths at register transfer level (RTL). A high-level synthesis scheme is proposed for producing such strongly self-testable data paths. This is achieved by incorporating testability constraints during processes of register assignment and interconnection assignment. This method is based on the use of test resources reusability to improve the self-testability of data path. Experimental results are presented to demonstrate the effectiveness of the proposed approach.

This paper presents a new BIST method for RTL data paths based on single-control testability a new concept of testability. The BIST method adopts hierarchical test. Test pattern generators are placed only on primary inputs and test patterns are propagated to and fed into each module. Test responses are similarly propagated to response analyzers placed only on primary outputs. For the propagation of test patterns and test responses, paths existing in the data path are utilized. The DFT method for the single-control testability is also proposed. The advantages of the proposed method are high fault coverage (for single stuck-at faults), low hardware overhead and capability of at-speed testing. Moreover test patterns generated by test pattern generators can be fed into each module at consecutive system clocks, and thus, the BIST can also detect some faults of other fault models (e.g., transition faults and delay faults) that require consecutive application of test patterns at the speed of the system clock.

We present a high-level synthesis method that considers weak testability of generated register-transfer level (RTL) data paths, as well as their area and performance. The weak testability, proposed in our previous work, is a testability measure of RTL data paths for nonscan design. We introduce a design objective for weak testability that is a condition on resource sharing sufficient for weak testability: We propose a heuristic synthesis algorithm that generates a weakly testable data path while minimizing area under a performance constraint.

This paper presents a non-scan design-for-testability method for controllers that are synthesized from FSMs (Finite State Machines). The proposed method can achieve complete fault efficiency: test patterns for a combinational circuit of a controller are applied to the controller using state transitions of the FSM. In the proposed method, at-speed test application can be performed and the test application time is shorter than previous methods. Moreover, experimental results show the area overhead is low.

We present a new non-scan DFT technique for register-transfer (RT) level data paths. In the technique, we add thru operations to some operational modules to make the data path easily testable. We define a testable measure, weak testability, and consider the problem to make the data path weakly testable with minimum hardware overhead. We also define a measure to estimate the test generation time. Experimental results show the effectiveness of our technique and the proposed measure.

Initialization of sequential circuits is one of time-consuming processes in test generation for sequential circuits, and hence synthesizing sequential circuits of which synchronizing sequences are short is an important approach to reducing the cost of test generation for the circuits. In this paper, we propose an approach to the synthesis of finite state machines (FSMs) with partial scan. We focus on repeating partial scan for synchronizing FSMs, and present an extended synchronizing sequence which consists of scan inputs and normal inputs, and which takes a circuit to a single specific state, regardless of the initial state. To synthesize synchronizable FSMs, we formulate a problem of minimizing extended synchronizing sequence length, and present a heuristic algorithm for the problem. We show the experimental results of the minimization of extended synchronizing sequence length on MCNC'91 benchmark FSMs. The experimental results show that the proposed heuristic algorithm can find a minimum-length extended synchronizing sequence for most of MCNC'91 benchmark FSMs, and the length of the extended synchronizing sequence is three or less for all the benchmark FSMs.

This paper considers distributed algorithms for distributed mobile systems. Many distributed algorithms have been designed for distributed systems consisting of static computers only. But most of them cannot be directly applied to mobile systems. This paper proposes a model of mobile systems. Management of movements of mobile hosts is abstracted in our model to simplify design of algorithms for mobile systems. This paper also defines the snapshot problem, one of the fundamental problems, on the model. The problem requires to find a strongly consistent configuration in which topological consistency is satisfied in addition to causal consistency. Furthermore, this paper presents a snapshot algorithm for mobile systems.