Narrow Results

The stable equivalent set is a finite collection of disjoint vertex subsets for a connected graph $G=(V(G),E(G))$ such that each set induces the same maximal independent set of $G$ and their union equals $V(G)$. The stable equivalence number is the maximum cardinality of the stable equivalent set $S$, and it is represented by the symbol $S_{\alpha }(G)$. In order to analyze the fault-tolerant and local metric dimensions of the intersection graph of gamma sets in the zero-divisor graph, $I_{\mathrm{\Gamma }}(R)$, the stable equivalent set of $I_{\mathrm{\Gamma }}(R)$ was used.

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 7.6|D_opt|+1.4, where D_opt is the minimum connected dominating set. The time complexity is O(k) rounds, where k is the depth of input BFS tree.

The star graph proposed by [1] has many advantages over the n-cube. However it suffers from having large gaps in the number of possible vertices. The (n,k)-star graph was proposed in [18] to address this issue. Since it is a generalization of the star graph, it retains many of the nice properties of the star graph. There are many different measures of structural integrity of interconnection networks. In this paper, we prove results of the following type for the (n,k)-star graph. If n + (r - 1)k - g(r) vertices are deleted from an (n,k)-star graph, the resulting graph will either be connected or has a large component and small components having at most r - 1 vertices in total. Additional results on conditional vertex connectivity and cycle connectivity will also be given.

A k-container of a graph G is a set of k internally disjoint paths between two distinct vertices. A k-container of G is a k*-container if it contains all vertices of G. A graph G is k*-connected if there exists a k*-container between any two distinct vertices, and a bipartite graph G is k*-laceable if there exists a k*-container between any two vertices from different partite sets of G. A k-connected graph (respectively, bipartite graph) G is super spanning connected (respectively, laceable) if G is r*-connected (r*-laceable) for any r with 1 ≤ r ≤ k. This paper shows that the two-dimensional torus Torus(m, n), m, n ≥ 3, is super spanning connected if at least one of m and n is odd and super spanning laceable if both m and n are even. Furthermore, the super spanning connectivity and spanning laceability of tori with faulty elements have been discussed.

Low-dimensional Tori are regularly used as interconnection networks in distributed-memory parallel computers. This paper investigates the fault-Hamiltonicity of two-dimensional Tori. A sufficient condition is derived for the graph Row-Torus(m, 2n + 1) with two faulty edges to have a Hamiltonian cycle, where m ≥ 3 and n ≥ 1. By applying the fault-Hamiltonicity of Row-Torus to a two-dimensional torus, we show that Torus(m, n), m, n ≥ 5, with at most four faulty edges is Hamiltonian if the following two conditions are satisfied: (1) the degree of every vertex is at least two, and (2) there do not exist a pair of nonadjacent vertices in a 4-cycle whose degrees are both two after faulty edges are removed.

In this paper, we study the fault-tolerant capability of hypercubes with respect to the hamiltonian property based on the concept of forbidden faulty sets. We show, with the assumption that each vertex is incident with at least three fault-free edges, that an $n$-dimensional hypercube contains a fault-free hamiltonian cycle, even if there are up to $(4n-13)$ edge faults. Moreover, we give an example to show that the result is optimal with respect to the number of edge faults tolerated.

Large scale synchronous network-on-chip (NoC) requires complex clock tree design, which leads to a large area overhead and power consumption. Based on handshaking protocols, asynchronous NoC does not have global clock tree distribution, which results in a natural power saving mode without any explicit clock gating. However, the faults occurring in such asynchronous networks will seriously affect their performances. In this paper, we propose AFTER, an Asynchronous Fault-TolErant Router, which uses the quasi delay insensitive (QDI) logic. The proposed router is able to detect the faults of ports and links. Then, a fault-tolerant routing mechanism, based on the port priority in different quadrants, is proposed to maximize the number of packets that can be transmitted via the shortest paths. In this way, the fault-tolerance of asynchronous routers can be achieved. Besides that, AFTER could also achieve high scalability, and is suitable for the large scale globally asynchronous locally synchronous (GALS) system. The experimental results show that, when faults occur in the network, AFTER has a better fault-tolerance performance than the reference.

Integration of safety-critical tasks with different certification requirements onto a common hardware platform has become a growing tendency in the design of real-time and embedded systems. In the past decade, great efforts have been made to develop techniques for handling uncertainties in task worst-case execution time, quality-of-service, and schedulability of mixed-criticality systems. However, few works take fault-tolerance as a design requirement. In this paper, we address the scheduling of fault-tolerant mixed-criticality systems to ensure the safety of tasks at different levels of criticalities in the presence of transient faults. We adopt task re-execution as the fault-tolerant technique. Extensive simulations were performed to validate the effectiveness of our algorithm. Simulation results show that our algorithm results in up to $15.8\%$ and $94.4\%$ improvement in system reliability and schedule feasibility as compared to existing techniques, which contributes to a more safe system.

Network-on-Chip (NoC) has become a promising design methodology for the modern on-chip communication infrastructure of many-core system. To guarantee the reliability of traffic, effective fault-tolerant scheme is critical to NoC systems. In this paper, we propose a fault-tolerant deflection routing (FTDR) to address faults on links and router by redundancy technique. The proposed FTDR employs backup links and a redundant fault-tolerant unit (FTU) at router-level to sustain the traffic reliability of NoC. Experimental results show that the proposed FTDR yields an improvement of routing performance and fault-tolerant capability over the reported fault-tolerant routing schemes in average flit deflection rate, average packet latency, saturation throughput and reliability by up to 13.5%, 9.8%, 10.6% and 17.5%, respectively. The layout area and power consumption are increased merely 3.5% and 2.6%.

The evolvable hardware (EHW) is widely used in the design of fault-tolerant system. Fault-tolerant system is really a real-time system, and the recovery time is necessary in fault detection and recovery. However, when applying EHW, real-time characteristic is usually ignored. In this paper, a fault-tolerant strategy based on EHW is proposed. The recovery time, predicted by the fault tree analysis (FTA), is considered as a constraint condition. A configuration library is set up in the design phase to accelerate the repair process of the anticipated faults. An evolvable algorithm (EA) based on similarity is applied to evolve the repair circuit for the unanticipated faults. When the library reaches the upper, the target system is reconfigured by the EA-repair technology. Extensive experiments are conducted to show that our method can improve the fault-tolerance of the system while satisfying the real-time requirement on FPGA platform. In a long run system, our method can keep a higher fault recovery rate.

Fault-tolerant Manhattan routing algorithms aim at finding a Manhattan path between the source and destination nodes and route around all faulty nodes. However, besides faulty nodes, some nonfaulty nodes that are helpless to make up a fault-tolerant Manhattan path should also be routed around. How to label such nonfaulty nodes efficiently is a major challenge. We propose a path-counter method. It can label such nodes with low time-complexity by counting every node’s fault-tolerant Manhattan paths to the source or destination node. During the path-counting procedure, no available nodes will be sacrificed under arbitrary fault distribution. Compared with fault-block model based work, our proposed method is independent of fault distribution, so its computational complexity is very low.

Due to technology scaling, reliability has become one of the biggest challenges in VLSI circuits. A number of techniques have been introduced in the literature, especially for arithmetic and logic unit in computers. One of well-known schemes for fault-tolerant arithmetic is the use of arithmetic residue codes. A key problem with most of the previous works regarding residue-based checker is that these methods impose an unacceptable area penalty. In this paper, we propose a novel residue checker with current mode multi-valued logic (CMMVL). A plain design procedure with arbitrary modulo is introduced; also a more efficient integrated scheme for modulo 3 has been demonstrated. The results of the plain CMMVL scheme showed up to 19.5% and 42.9% lower delay and power consumption, respectively, compared with those of the conventional CMOS. Also, utilizing the integrated CMMVL provided, on average, about 17.7% and 80.2% lower delay and power consumption, respectively.

Precise distributed clock synchronization is important for Time-Triggered Ethernet (TTEthernet) in which fail-arbitrary synchronization failure cannot be treated by existed protocols unless every synchronization node is equipped with a dedicated clock monitoring. A novel method was presented to detect arbitrary synchronization failure by some application-level routines which make distributed decisions mainly by monitoring the protocol control frames (PCFs). An arbitrary failure node can be exactly detected and located by the routine resided on each of the Compression Masters based on the concerned accusation messages sent from Synchronization Masters or Synchronization Clients. The proposed method can make up the weak points on the detection of the arbitrary failure node of the existed fault-tolerant synchronization mechanism and enhance the synchronization node to resist the arbitrary failure for TTEthernet. By our SAL-based model checking, this method had been formally verified to have a fail-arbitrary detection capacity even in a standard integration configuration. Simulations imply that the quality of the whole clock synchronization is effectively improved after the failure node has been isolated.

The distribution energy router (DER) is the core of the interacted and interconnected micro grid in future distribution network, which fully meets the needs of the ubiquitous power internet of things (IOT) based future distribution network. The reliability of micro grid which applies the DER is highly related to its cascaded full-bridge converters. With the redundant full-bridge converters and IOT technology, the DER can stand the component failures, hence improve the robustness of the DER as well as the future interacted and interconnected micro grid. For a ubiquitous power IOT technology based DER, this paper proposes a redundancy design for fault tolerant strategy. Several redundancy designs are discussed in detail with operational principles and control strategies. The proposed redundancy design is implemented on the power circuit of one phase for DER consists of a nine-level cascaded full-bridge converter in Saber simulation platform, and the simulation results prove that the redundancy design can minimize the customer’s power interrupt time and the consequent damages to the system.

We present some results concerning hamiltonian properties of recursive circulant graphs in the presence of faulty vertices and/or edges. The recursive circulant graph G(N, d) with d ≥ 2 has vertex set V(G) = {0, 1, …, N - 1} and the edge set E(G) = {(v, w)| ∃ i, 0 ≤ i ≤ ⌈ log_d N⌉ - 1, such that v = w + dⁱ (mod N)}. When N = cd^k where d ≥ 2 and 2 ≤ c ≤ d, G(cd^k, d) is regular, node symmetric and can be recursively constructed. G(cd^k, d) is a bipartite graph if and only if c is even and d is odd. Let F, the faulty set, be a subset of V(G(cd^k, d)) ∪ E(G(cd^k, d)). In this paper, we prove that G(cd^k, d) - F remains hamiltonian if |F| ≤ deg(G(cd^k, d)) - 2 and G(cd^k, d) is not bipartite. Moreover, if |F| ≤ deg(G(cd^k, d)) - 3 and G(cd^k, d) is not a bipartite graph, we prove a more stronger result that for any two vertices u and v in V(G(cd^k, d)) - F, there exists a hamiltonian path of G(cd^k, d) - F joining u and v.

The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices as maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we show that an (n-1)-regular Cayley graph generated by transposition tree is maximally local-connected, even if there are at most (n-3) faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.

In this paper, we consider the conditionally faulty graphs G that each vertex of G is incident with at least m fault-free edges, 2 ≤ m ≤ n - 1. We extend the limitation m ≥ 2 in all previous results of edge-bipancyclicity with faulty edges and faulty vertices. Let f_e (respectively, f_v) denotes the number of faulty edges (respectively, faulty vertices) in an n-dimensional hypercube Q_n. For all m, we show that every fault-free edge of Q_n lies on a fault-free cycle of every even length from 4 to |V| - 2f_v inclusive provided f_e + f_v ≤ n - 2. This result is not only optimal, but also improves on the previously best known results reported in the literature.

Based on the quantum key distribution protocol [X. H. Li, F. G. Deng and H. Y. Zhou, Phys. Rev. A78 (2008) 022321], we proposed two efficient fault-tolerant quantum secret sharing schemes over two collective-noise channels, in which the sharers can establish a key with the sender only if all the sharers collaborate together. Noiseless subspaces are composed of two Bell states based on the hypothesis of collective noise and the spatial degree of freedom is introduced to insure the security. Although entangled states are used to encode the key bits, the sharers are only required to perform single-particle product operations or single-particle product measurement, making the schemes convenient with current technique. As there is no basis mismatch during the measurement, almost all of the samples can be used to share the key.

The folded hypercube is a well-known variation of hypercube structure and can be constructed from a hypercube by adding an edge to every pair of vertices with complementary addresses. Let ${FF}_v$ (respectively, ${FF}_e$) denote the set of faulty vertices (respectively, faulty edges) in an $n$-dimensional folded hypercube $F{Q}_n$. In the case that all edges in $F{Q}_n$ are fault-free, Cheng et al. [Cycles embedding on folded hypercubes with faulty vertices, Discrete Appl. Math.161 (2013) 2894–2900] has shown that (1) every fault-free edge of ${FQ}_n-{FF}_v$ lies on a fault-free cycle of every even length from $4$ to $2^n-2\left|{FF}_v\right|$ if $\left|{FF}_v\right|\le n-2$, where $n\ge 3$; and (2) every fault-free edge of ${FQ}_n-{FF}_v$ lies on a fault-free cycle of every odd length from $n+1$ to $2^n-2\left|{FF}_v\right|-1$ if $\left|{FF}_v\right|\le n-2$, where $n\ge 2$ is even. In this paper, we extend Cheng’s result to obtain two further properties, which consider both vertex and edge faults, as follows:

(1) Every fault-free edge of $F{Q}_n-{FF}_v-{FF}_e$ lies on a fault-free cycle of every even length from $4$ to $2^n-2\left|{FF}_v\right|$ if $\left|{FF}_v\right|+\left|{FF}_e\right|\le n-2$, where $n\ge 3$;

(2) Every fault-free edge of $F{Q}_n-{FF}_v-{FF}_e$ lies on a fault-free cycle of every odd length from $n+1$ to $2^n-2\left|{FF}_v\right|-1$ if $\left|{FF}_v\right|+\left|{FF}_e\right|\le n-2$, where $n\ge 2$ is even.

A locating-dominating set is a subset of vertices representing “detectors” in a graph G which can locate an “intruder” given that each detector covers its closed neighborhood and can distinguish its own location from its neighbors. We explore a fault-tolerant variant of locating-dominating sets, called error-detecting locating-dominating (DET:LD) sets, which can tolerate one false negative. The concept of DET:LD sets was originally introduced in 2002, along with several properties in various classes of graphs; we extend this work by fully characterizing DET:LD sets for general graphs and establishing existence criteria. We prove that the problem of determining the minimum density of a DET:LD set in arbitrary graphs is NP-complete. Additionally, we determine that the minimum density in cubic graphs is at least $\frac{3}{5}$, and we show an infinite family of cubic graphs achieving this density.