A fault-tolerant aggregate signature (FT-AS) scheme is a variant of an aggregate signature scheme with the additional functionality to trace signers that create invalid signatures in case an aggregate signature is invalid. Several FT-AS schemes have been proposed so far, and some of them trace such rogue signers in multi-rounds, i.e., the setting where the signers repeatedly send their individual signatures. However, it has been overlooked that there exists a potential attack on the efficiency of bandwidth consumption in a multi-round FT-AS scheme. Since one of the merits of aggregate signature schemes is the efficiency of bandwidth consumption, such an attack might be critical for multi-round FT-AS schemes. In this paper, we propose a new multi-round FT-AS scheme that is tolerant of such an attack. We implement our scheme and experimentally show that it is more efficient than the existing multi-round FT-AS scheme if rogue signers randomly create invalid signatures with low probability, which for example captures spontaneous failures of devices in IoT systems.

It is very important to design an embedded real-time system as a fault-tolerant system to ensure dependability. In particular, when a power failure occurs, restart processing after power restoration is required in a real-time system using a conventional processor. Even if power is restored quickly, the restart process takes a long time and causes deadline misses. In order to design a fault-tolerant real-time system, it is necessary to have a processor that can resume operation in a short time immediately after power is restored, even if a power failure occurs at any time. Since current embedded real-time systems are required to execute many tasks, high schedulability for high throughput is also important. This paper proposes a non-stop microprocessor architecture to achieve a fault-tolerant real-time system. The non-stop microprocessor is designed so as to resume normal operation even if a power failure occurs at any time, to achieve little performance degradation for high schedulability even if checkpoint creations and restorations are performed many times, to control flexibly non-volatile devices through software configuration, and to ensure data consistency no matter when a checkpoint restoration is performed. The evaluation shows that the non-stop microprocessor can restore a checkpoint within 5µsec and almost hide the overhead of checkpoint creations. The non-stop microprocessor with such capabilities will be an essential component of a fault-tolerant real-time system with high schedulability.

Aggregate signature schemes enable us to aggregate multiple signatures into a single short signature. One of its typical applications is sensor networks, where a large number of users and devices measure their environments, create signatures to ensure the integrity of the measurements, and transmit their signed data. However, if an invalid signature is mixed into aggregation, the aggregate signature becomes invalid, thus if an aggregate signature is invalid, it is necessary to identify the invalid signature. Furthermore, we need to deal with a situation where an invalid sensor generates invalid signatures probabilistically. In this paper, we introduce a model of aggregate signature schemes with interactive tracing functionality that captures such a situation, and define its functional and security requirements and propose aggregate signature schemes that can identify all rogue sensors. More concretely, based on the idea of Dynamic Traitor Tracing, we can trace rogue sensors dynamically and incrementally, and eventually identify all rogue sensors of generating invalid signatures even if the rogue sensors adaptively collude. In addition, the efficiency of our proposed method is also sufficiently practical.

This paper addresses the problem of developing an efficient fault-tolerant routing method for 2D mesh Network-on-Chips (NoCs) to realize dependable and high performance many core systems. Existing fault-tolerant routing methods have two critical problems of high communication latency and low node utilization. Unlike almost all existing methods where packets always detour faulty nodes, we propose a novel and unique approach that packets can pass through faulty nodes. For this approach, we enhance the common NoC architecture by adding switches and links around each node and propose a fault-tolerant routing method with no virtual channels based on the well-known simple XY routing method. Simulation results show that the proposed method reduces average communication latency by about 97.1% compared with the existing method, without sacrificing fault-free nodes.

High availability is crucial for industrial Ethernet networks and Ethernet-based control systems, such as automation networks and substation automation systems. Because the standard Ethernet does not support fault tolerance capability, the high availability of Ethernet networks can be increased by using redundancy protocols. Various redundancy protocols for Ethernet networks have been developed and standardized, such as rapid spanning tree protocol (RSTP), media redundancy protocol (MRP), parallel redundancy protocol (PRP), high-availability seamless redundancy (HSR), and others. RSTP and MRP provide redundancy in the network, whereas PRP and HSR provide redundancy in the end nodes. RSTP and MRP have a disadvantage in switchover delay. PRP and HSR provide zero recovery time, but PRP requires a duplicate network infrastructure, and HSR is mainly used in ring-based topologies. Additionally, PRP and HSR provide seamless redundancy in the end nodes and are applied in dedicated HSR networks with dedicated HSR nodes. In this paper, we present a novel seamless redundancy protocol for Ethernet networks, which is called the Redundancy Protocol for Ethernet (RPE). The RPE provides seamless redundancy in the network. This protocol not only provides seamless communications with zero switchover time in case of failure but also supports all topologies. The RPE is transparent and compatible with standard Ethernet nodes. These features make the RPE very useful in time-critical and mission-critical systems, such as substation automation systems, automation networks, and other industrial Ethernet networks.

Two spanning trees T1,T2 of a graph G = (V,E) are independent if they are rooted at the same vertex, say r, and for each vertex v ∈ V, the path from r to v in T1 and the path from r to v in T2 have no common vertices and no common edges except for r and v. In general, spanning trees T1,T2,…,Tk of a graph G = (V,E) are independent if they are pairwise independent. A graph G = (V,E) is called a 2-chordal ring and denoted by CR(N,d1,d2), if V = {0,1,…,N-1} and E = {(u,v)|[v-u]N = 1 or [v-u]N = d1 or [v-u]N = d2, 2 ≤ d1 < d2 ≤ N/2}. CR(N,d1,N/2) is 5-connected if N ≥ 8 is even and d1 ≠ N/2-1. We give an algorithm to construct 5 independent spanning trees of CR(N,d1,N/2),N ≥ 8 is even and 2 ≤ d1 ≤ ⌈N/4⌉.

Nowadays, fault tolerance has been playing a progressively important role in covering increasing soft/hard error rates in electronic devices that accompany the advances of process technologies. Research shows that wear-out faults have a gradual onset, starting with a timing fault and then eventually leading to a permanent fault. Error detection is thus a required function to maintain execution correctness. Currently, however, many highly dependable methods to cover permanent faults are commonly over-designed by using very frequent checking, due to lack of awareness of the fault possibility in circuits used for the pending executions. In this research, to address the over-checking problem, we introduce a metric for permanent defects, as operation defective probability (ODP), to quantitatively instruct the check operations being placed only at critical positions. By using this selective checking approach, we can achieve a near-100% dependability by having about 53% less check operations, as compared to the ideal reliable method, which performs exhaustive checks to guarantee a zero-error propagation. By this means, we are able to reduce 21.7% power consumption by avoiding the non-critical checking inside the over-designed approach.

In this paper, we present a new fault-tolerant, large-scale star network scheme called Scalable Autonomous Fault-tolerant Ethernet (SAFE). The primary goal of a SAFE scheme is to provide network scalability and autonomous fault detection and recovery. SAFE divides a large-scale, mission-critical network, such as the naval combatant network, into several subnets by limiting the number of nodes in each subnet. This network can be easily configured as a star network in order to meet fault recovery time requirements. For SAFE, we developed a novel mechanism for inter-subnet fault detection and recovery; a conventional Ethernet-based heartbeat mechanism is used in each subnet. Theoretical and experimental performance analyses of SAFE in terms of fail-over time were conducted under various network failure scenarios. The results validate our scheme.

Manufacturing defects in the deep sub-micron VLSI process and aging resulted problems of devices during lifecycle are inevitable, and fault-tolerant routing algorithms are important to provide the required communication for NoCs in spite of failures. The proposed algorithm, referred to as scalable and reconfigurable fault-tolerant distributed routing (RFDR), partitions the system into nine regions using the concept of divide-and-conquer. It is a distributed algorithm, and each router guarantees fault-tolerance within one's own region and the system can be still sustained with multiple fault areas. The proposed RFDR has excellent scalability with hardware cost keeping constant independent of system size. Also it is completely reconfigurable when new nodes fail. Simulations under various synthetic traffic patterns show its better performance compared to Extended-XY routing algorithm. Moreover, there is almost no hardware overhead compared to Logic-Based Distributed Routing (LBDR), but the fault-tolerance capacity is enhanced in the proposed algorithm. Hardware cost is reduced 37% compared to Reconfigurable Distributed Scalable Predictable Interconnect Network (R-DSPIN) which only supports single fault region.

The Network-on-Chip (NoC) is limited by the reliability constraint, which impels us to exploit the fault-tolerant routing. Generally, there are two main design objectives: tolerating more faults and achieving high network performance. To this end, we propose a new multiple-round dimension-order routing (NMR-DOR). Unlike existing solutions, besides the intermediate nodes inter virtual channels (VCs), some turn-legally intermediate nodes inside each VC are also utilized. Hence, more faults are tolerated by those new introduced intermediate nodes without adding extra VCs. Furthermore, unlike the previous solutions where some VCs are prioritized, the NMR-DOR provides a more flexible manner to evenly distribute packets among different VCs. With extensive simulations, we prove that the NMR-DOR maximally saves more than 90% unreachable node pairs blocked by faults in previous solutions, and significantly reduces the packet latency compared with existing solutions.

In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.

We propose a Fault-Tolerant Object Group framework that provides group management and fault-tolerance services for consistency maintenance and state transparency as well. Through a virtual home-network simulation, we validate that the FTOG framework supports both of the reliability and the stability of the distributed home-network systems.

We consider the problem of computing the optimal swap edges of a shortest-path tree. This problem arises in designing systems that offer point-of-failure shortest-path rerouting service in presence of a single link failure: if the shortest path is not affected by the failed link, then the message will be delivered through that path; otherwise, the system will guarantee that, when the message reaches the node where the failure has occurred, the message will then be re-routed through the shortest detour to its destination. There exist highly efficient serial solutions for the problem, but unfortunately because of the structures they use, there is no known (nor foreseeable) efficient distributed implementation for them. A distributed protocol exists only for finding swap edges, not necessarily optimal ones. We present two simple and efficient distributed algorithms for computing the optimal swap edges of a shortest-path tree. One algorithm uses messages containing a constant amount of information, while the other is tailored for systems that allow long messages. The amount of data transferred by the protocols is the same and depends on the structure of the shortest-path spanning-tree; it is no more, and sometimes significantly less, than the cost of constructing the shortest-path tree.

Because fault-based attacks on cryptosystems have been proven effective, fault diagnosis and tolerance in cryptography have started a new surge of research and development activity in the field of applied cryptography. Without magnitude comparisons, the Montgomery multiplication algorithm is very attractive and popular for Elliptic Curve Cryptosystems. This paper will design a Montgomery multiplier array with a bit-parallel architecture in GF(2m) with concurrent error detection capability to protect it against fault-based attacks. The robust Montgomery multiplier array with concurrent error detection requires only about 0.2% extra space overhead (if m=512 is as an example) and requires four extra clock cycles compared to the original Montgomery multiplier array without concurrent error detection.

The paper presents HiPeer, a robust resource distribution and discovery algorithm that can be used for fast and fault-tolerant location of resources in P2P network environments. HiPeer defines a concentric multi-ring overlay networking topology, whereon dynamic network management methods are deployed. In terms of performance, HiPeer delivers of number of lowest bounds. We demonstrate that for any De Bruijn digraph of degree d 2 and diameter DDB HiPeer constructs a highly reliable network, where each node maintains a routing table with at most 2d+2 entries independent of the number N of nodes in the system. Further, we show that any existing resource in the network with at most d nodes can be found within at most DHiPeer = log d(N(d-1)+d)-1 overlay hops. This result is as close to the Moore bound [1] as the query path length in other outstanding P2P proposals based on the De Bruijn digraphs. Thus, we argue that HiPeer defines a highly connected network with connectivity d and the lowest yet known lookup bound DHiPeer. Moreover, we show that any node's "join or leave" operation in HiPeer implies a constant expected reorganization cost of the magnitude order of O(d) control messages.

This paper presents a Fault-Tolerant Object Group (FTOG) model that provides the group management service and the fault-tolerance service for consistency maintenance and state transparency. Through Intelligent Home Network Simulator, we verify that FTOG model supports both of reliability and the stability of the distributed system.

This paper proves that for every positive integers n,k and any positive number ε, we can explicitly construct a DAG G with n+O(k1+ε) vertices and a constant degree such that even after removing any k vertices from G, the remaining digraph still contains an n-vertex dipath. This paper also proves that for every positive integers n,k and any positive number ε, we can explicitly construct a graph H with n+O(k2+ε) vertices and a constant degree such that even after removing any k vertices from H, the remaining graph still contains an n-vertex 2-dimensional square mesh.

In mobile multimedia environment, it is very important to minimize handoff latency due to mobility. In terms of reducing handoff latency, Hierarchical Mobile IPv6 (HMIPv6) can be an efficient approach, which uses a mobility agent called Mobility Anchor Point (MAP) in order to localize registration process. However, MAP can be a single point of failure or performance bottleneck. In order to provide mobile users with satisfactory quality of service and fault-tolerant service, it is required to cope with the failure of mobility agents. In, we proposed Robust Hierarchical Mobile IPv6 (RH-MIPv6), which is an enhanced HMIPv6 for fault-tolerant mobile services. In RH-MIPv6, an MN configures two regional CoA and registers them to two MAPs during binding update procedures. When a MAP fails, MNs serviced by the faulty MAP (i.e., primary MAP) can be served by a failure-free MAP (i.e., secondary MAP) by failure detection/recovery schemes in the case of the RH-MIPv6. In this paper, we investigate the comparative study of RH-MIPv6 and HMIPv6 under several performance factors such as MAP unavailability, MAP reliability, packet loss rate, and MAP blocking probability. To do this, we utilize a semi-Markov chain and a M/G/C/C queuing model. Numerical results indicate that RH-MIPv6 outperforms HMIPv6 for all performance factors, especially when failure rate is high.

In this paper we study a classical firing squad synchronization problem on a model of fault-tolerant cellular automata that have possibly some defective cells. Several fault-tolerant time-efficient synchronization algorithms are developed based on a simple freezing-thawing technique. It is shown that, under some constraints on the distribution of defective cells, any cellular array of length n with p defective cell segments can be synchronized in 2n - 2 + p steps.

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 heuristic solution to the problem. Our algorithm is constructed by four layered modules (sub-algorithms): construction of a shortest path forest, transformation of the network, construction of a minimum spanning tree, and pruning unnecessary links and processes. Competitiveness is 2(1-1/l), where l is the number of leaves of optimal solution.