Narrow Results

The $k$-set tree connectivity, as a natural extension of classical connectivity, is a very important index to evaluate the fault-tolerance of interconnection networks. Let $G=(V,E)$ be a connected graph and a subset $S\subseteq V$, an $S$-tree of graph $G$ is a tree $T=(V^{\prime },E^{\prime })$ that contains all the vertices of $S$ and $E(T)\subseteq E(G)$. Two $S$-trees $T$ and $T^{\prime }$ are internally disjoint if and only if $E(T)\cap E(T^{\prime })=\varnothing$ and $V(T)\cap V(T^{\prime })=S$. The cardinality of maximum internally disjoint $S$-trees is defined as ${\kappa }_G(S)$, and the $k$-set tree connectivity is defined by ${\kappa }_k(G)=min\{{\kappa }_G(S)|S\subseteq V(G)\text{and}\left|S\right|=k\}$. In this paper, we show that the $k$-set tree connectivity of folded hypercube when $k=4$, that is, ${\kappa }_4(F{Q}_n)=n$, where $F{Q}_n$ is folded hypercube for $n\ge 2$.

The connectivity of a network is an important indicator for assessing its reliability and fault-tolerability. In this paper, we study a novel measurement, which is $h$-faulty-block connectivity. Let $G$ be a connected graph, $C\subset V(G)$ and $G[C]$ be a connected subgraph. Then, $C$ is called an $h$-fault-block of $G$ if $G-C$ is disconnected, and every component of $G-C$ has at least $h+1$ nodes with a non-negative integer $h$. The minimum cardinality over all $h$-fault-blocks of $G$ is called $h$-fault-block connectivity of $G$, denoted by $F{B}_{k_h}(G)$. In this paper, we determine $F{B}_{k_h}(B{H}_n)$ for $n$-dimensional balanced hypercube $B{H}_n$, a variation of the hypercube. We prove that $F{B}_{k_0}(B{H}_n)=2n+1$ for $n\ge 2$, $F{B}_{k_1}(B{H}_n)=4n-2$ for $n\ge 3$, and $F{B}_{k_2}(B{H}_n)=6n-5$ for $n\ge 4$.

The connectivity of a network is an important indicator for assessing its reliability and fault-tolerability. In this paper, we study a novel measure, which is $h$-faulty-block connectivity. Given a connected graph $G$ and a non-negative integer $h$, let $C\subset V(G)$ and $G[C]$ be connected subgraphs. Then, $C$ is called an $h$-faulty-block of $G$ if $G-C$ disconnects $G$, and every remaining component of $G-C$ has at least $h+1$ nodes. The minimum cardinality over all $h$-faulty-blocks of $G$ is called $h$-faulty-block connectivity of $G$, denoted by $F{B}_{k_h}(G)$. In this paper, we focus on the locally twisted cube $LT{Q}_n$. We study the $\{0,1,2\}$-faulty-block connectivity of $LT{Q}_n$ and show that $F{B}_{k_0}(LT{Q}_n)=2n-1$ for $n\ge 5$, $F{B}_{k_1}(LT{Q}_n)=3n-4$ for $n\ge 5$, and $F{B}_{k_2}(LT{Q}_n)=4n-7$ for $n\ge 7$.

In numerical computations, the method of divided differences is a very important technique for polynomial approximations. Consider a pipelined divided–difference computation for approximating an nth degree polynomial. This paper first presents a method to transform the computational structure of divided differences into the pyramid tree with nodes. Based on graph embedding technique, without any extra communication delay, the pipelined divided–difference computation can be performed in a (2k + 1)-dimensional fault–free hypercube for n + 1 = 2^k + t, k > 0, and 0 < t < 2^k; the pipelined divided-difference computation can be further performed in a (2k + 2)-dimensional faulty hypercube to tolerate arbitrary (k - 1) faulty nodes/links. To the best of our knowledge, this is the first time such mapping methods are being proposed in the literature.

We analyse the fault-tolerant parameters and topological properties of a hierarchical network of hypercubes. We take a close look at the Extended Hypercube (EH) and the Hyperweave (HW) architectures and also compare them with other popular architectures. These two architectures have low diameter and constant degree of connectivity making it possible to expand these networks without affecting the existing configuration. A scheme for incrementally expanding this network is also presented. We also look at the performance of the ASCEND/DESCEND class of algorithms on these architectures.

Chandra and Toueg proposed in 1993 a new approach to overcome the impossibility of reaching deterministically Consensus — and by corollary Atomic Broadcast — in asynchronous systems subject to crash failures. They augment the asynchronous system with a possibly Unreliable Failure Detector which provides some information about the operational state of processes. In this paper, we present an extension of the Consensus problem that we call Uniform Prefix Agreement. This extension enables all the processes to propose a flow of messages during an execution — instead of one as in the Consensus problem — and uses all these proposed messages to compose the decision value. Prefix Agreement is based on an Unreliable Failure Detector. We use repeated executions of Prefix Agreement to build an efficient Uniform Atomic Broadcast algorithm. This paper describes the Uniform Prefix Agreement and Uniform Atomic Broadcast algorithms, and provides proofs of their correctness.

In this paper, we address the problem of k-out-of-ℓ exclusion, a generalization of the mutual exclusion problem, in which there are ℓ units of a shared resource, and any process can request up to k units (1 ≤ k ≤ ℓ). A protocol is self-stabilizing if, starting from an arbitrary configuration, be it initial state or after a corrupted state, the protocol can start behaving normally within a finite time. We propose the first deterministic self-stabilizing distributed k-out-of-ℓ exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process.

Topology embedding enables one 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 in real topology. The proposed protocol improves the execution slowdown of previous two protocols [19, 20] and provides adaptive message delivery delay on the emulated channels, which is a new type of adaptability against transient faults.

A self-stabilizing algorithm is a distributed algorithm that can start from any initial (legitimate or illegitimate) state and eventually converge to a legitimate state in finite time without being assisted by any external agent. In this paper, we propose a self-stabilizing algorithm for finding the 3-edge-connected components of an asynchronous distributed computer network. The algorithm stabilizes in O(dnΔ) rounds and every processor requires O(nlogΔ) bits, where Δ(≤ n) is an upper bound on the degree of a node, d(≤ n) is the diameter of the network, and n is the total number of nodes in the network. These time and space complexity are at least a factor of n better than those of the previously best-known self-stabilizing algorithm for 3-edge-connectivity. The result of the computation is kept in a distributed fashion by assigning, upon stabilization of the algorithm, a component identifier to each processor which uniquely identifies the 3-edge-connected component to which the processor belongs. Furthermore, the algorithm is designed in such a way that its time complexity is dominated by that of the self-stabilizing depth-first search spanning tree construction in the sense that any improvement made in the latter automatically implies improvement in the time complexity of the algorithm.

Self-stabilization is a strong property, which guarantees that a distributed system always resumes a correct behavior starting from an arbitrary initial state. Since it is a strong property, some problems cannot have self-stabilizing solutions. Weaker guarantees hence have been later introduced to cope with impossibility results, e.g., probabilistic self-stabilization only guarantees probabilistic convergence to a correct behavior, and weak stabilization only guarantees the possibility of convergence. In this paper, we investigate the relative power of self, probabilistic, and weak stabilization, with respect to the set of problems that can be solved. Weak stabilization is by definition stronger than self-stabilization and probabilistic self-stabilization in that precise sense. We first show that weak stabilization allows to solve problems having no self-stabilizing solution. We then show that any finite state deterministic weak stabilizing algorithm to solve a problem under the strongly fair scheduler is always a probabilistic self-stabilizing algorithm to solve the same problem under the randomized scheduler. Unfortunately, this good property does not hold in general for infinite state algorithms. We however show that for some classes of infinite state algorithms, this property holds. These results hint at more practical use of weak stabilizing algorithms, as they are easier to design and prove their correctness than their self-stabilizing and probabilistic self-stabilizing counterparts.

In computer networks area, the minimal dominating sets (MDS) and maximal independent sets (MIS) structures are very useful for creating virtual network overlays. Often, these set structures are used for designing efficient protocols in wireless sensor and ad-hoc networks. In this paper, we give a particular interest to one kind of these sets, called Independent Strong Dominating Set (ISD-set).

In addition to its domination and independence properties, the ISD-set considers also node’s degrees that make it very useful in practical applications where nodes with larger degrees play important role in the networks. For example, some network clustering protocols chose nodes with large degrees to be cluster-heads, which is exactly the result obtained by an ISD-set algorithm. Thence, we propose the first distributed self-stabilizing algorithm for computing an ISD-set of an arbitrary graph (called ISDS). Then, we prove that ISDS algorithm operates under the unfair distributed scheduler and converges after at most $(n+1)$ rounds requiring only $O\left(\mathrm{\text{log}}\mathrm{\Delta }\right)$ space memory per node where Δ is the maximum node degree. The complexity of ISDS algorithm in rounds has the same order as the best known self-stabilizing algorithms for finding MDS and MIS. Moreover, performed simulations and comparisons with well-known self-stabilizing algorithms for MDS and MIS problems showed the efficiency of ISDS, especially for reducing the cardinality of dominating sets founded by the algorithms.

Computing over large platforms calls for the ability to maintain distributed structures at large scale. Among the many different structures proposed in this context, the prefix tree structure has been identified as an adequate one for indexing and retrieving information. One weakness of using such a distributed structure stands in its poor native fault tolerance, leading to the use of preventive costly mechanisms such as replication.

Self-stabilization is a suitable approach to design reliable solutions for dynamic systems, and was recently enhanced with new models to be able to deal with large scale dynamic platforms. A self-stabilizing system is guaranteed to reach a correct configuration, whatever its initial state is. Following this path, it is becoming possible to make distributed structures self-stabilizing at large scale.

In this paper, we focus on making tries self-stabilizing over such platforms, and propose a self-stabilizing maintenance algorithm for a prefix tree using a message passing model. The proof of self-stabilization is provided, and simulation results are given, to better capture its performances. Still based on simulations, we provide evidences that the protocol, beyond its capacity to repair the structure, can significantly improve the system’s availability, even when the system is not yet stabilized.

The problem of two node-disjoint paths is to identify two paths ${{𝒬}}_1$ and ${{𝒬}}_2$ from source $s\in V$ to target $t\in V$ without any common intermediate node in a communication network $G=(V,E)$, where each node (vertex) in $V$ denotes a process and each edge $(p,q)\in E$ denotes a communication channel between nodes $p$ and $q$. In this paper, we present the first adaptive stabilizing algorithm for finding a pair of node-disjoint paths in a semi-anonymous arbitrary network in $O(D)$ rounds and the state-space complexity is $O(logD)$ bits per process, where $D$ is the diameter of the communication network. The algorithm assumes weakly fair distributed daemon and the knowledge of an upper bound on the number of processes by each process. If two disjoint paths exist between $s$ and $t$, two disjoint paths are guaranteed to be constructed. In addition, the algorithm detects if two node-disjoint paths exist or not. Since the proposed algorithm is stabilizing, it does not require initialization and is capable of withstanding transient faults. We view a fault that perturbs the state of the system but not its program as a transient fault. The proposed algorithm has a wide range of applications in ensuring reliability and security of sensor, mobile and fixed communication networks.

Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size $N$ using $O(\sqrt{N})$ queries. It provides a significant speed-up over any classical algorithm [3].

The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6].

We study the behavior of Grover’s algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in $O(\sqrt{N})$ queries.

We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of a limiting state ${\rho }_{lim}$.

Fault tolerance is an important issue in interconnection networks, and the traditional edge connectivity is an important measure to evaluate the robustness of an interconnection network. The component edge connectivity is a generalization of the traditional edge connectivity. The $g$-component edge connectivity $c{\lambda }_g(G)$ of a non-complete graph $G$ is the minimum number of edges whose deletion results in a graph with at least $g$ components. Let $g$ be an integer and $g={\sum }_{i=0}^s{2}^{t_i}$ be the decomposition of $g$ such that $t_0=[{\mathrm{\text{log}}}_{2}g],$ and $t_i=[{\mathrm{\text{log}}}_2(g-{\sum }_{r=0}^{i-1}{2}^{t_r})]$ for $i\ge 1$. In this note, we determine the $g$-component edge connectivity of the hypercube $Q_n$, $c{\lambda }_g(Q_n)=ng-({\sum }_{i=0}^s{t}_i{2}^{t_i-1}+{\sum }_{i=0}^{s}i\cdot 2^{t_i})$ for $g\le 2^{[\frac{n}{2}]}+1,n\ge 7$. Moreover, we classify the corresponding optimal solutions.

The balanced hypercube, $B{H}_n$, is a variant of hypercube $Q_n$. Zhou et al. [Inform. Sci.300 (2015) 20–27] proposed an interesting problem that whether there is a fault-free Hamiltonian cycle in ${BH}_n$ with each vertex incident to at least two fault-free edges. In this paper, we consider this problem and show that each fault-free edge lies on a fault-free Hamiltonian cycle in ${BH}_n$ after no more than $4n-5$ faulty edges occur if each vertex is incident with at least two fault-free edges for all $n\ge 2$. Our result is optimal with respect to the maximum number of tolerated edge faults.

The connectivity plays an important role in measuring the fault tolerance and reliability of interconnection networks. The generalized $k$-connectivity of a graph $G$, denoted by ${\kappa }_k(G)$, is an important indicator of a network’s ability for fault tolerance and reliability. The bubble-sort star graph, denoted by ${BS}_n$, is a well known interconnection network. In this paper, we show that ${\kappa }_3({BS}_n)=2n-4$ for $n\ge 3$, that is, for any three vertices in ${BS}_n$, there exist $2n-4$ internally disjoint trees connecting them in ${BS}_n$ for $n\ge 3$, which attains the upper bound of ${\kappa }_3(G)\le \delta (G)-1$ given by Li et al. for $G={BS}_n$.

An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processors and communication links, respectively. Connectivity is an important metric for fault tolerance of interconnection networks. A graph $G$ is said to be maximally local-connected if each pair of vertices $u$ and $v$ are connected by $min\{d_G(u),d_G(v)\}$ vertex-disjoint paths. In this paper, we show that Cayley graphs generated by $m$($\ge 7$) transpositions are $(m-2)$-fault-tolerant maximally local-connected and are also $(m-3)$-fault-tolerant one-to-many maximally local-connected if their corresponding transposition generating graphs have a triangle, $(m-2)$-fault-tolerant one-to-many maximally local-connected if their corresponding transposition generating graphs have no triangles. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, Cayley graphs generated by $m$($\ge 7$) transpositions are $(m-1)$-fault-tolerant maximally local-connected if their corresponding transposition generating graphs have no triangles.

The $k$-ary $n$-cube network is known as one of the most attractive interconnection networks for parallel and distributed systems. A many-to-many $m$-disjoint path cover ($m$-DPC for short) of a graph is a set of $m$ vertex-disjoint paths joining two disjoint vertex sets $S$ and $T$ of equal size $m$ that altogether cover every vertex of the graph. The many-to-many $m$-DPC is classified as paired if each source in $S$ is further required to be paired with a specific sink in $T$, or unpaired otherwise. In this paper, we consider the unpaired many-to-many $m$-DPC problem of faulty bipartite $k$-ary $n$-cube networks $Q_n^k$, where the sets $S$ and $T$ are chosen in different parts of the bipartition. We show that, every bipartite $Q_n^k$, under the condition that $f$ or less faulty edges are removed, has an unpaired many-to-many $m$-DPC for any $f$ and $m\ge 1$ subject to $f+m\le 2n-1$. The bound $2n-1$ is tight here.

With the rapid development and advances of very large scale integration technology and wafer-scale integration technology, multiprocessor systems, taking interconnection networks as underlying topologies, have been widely designed and used in big data era. The topology of an interconnection network is usually represented as a graph. If any two distinct vertices $x,y$ in a connected graph $G$ are connected by min$\{{\mathrm{\text{deg}}}_G(x),{\mathrm{\text{deg}}}_G(y)\}$ vertex (edge)-disjoint paths, then $G$ is called strongly Menger (edge) connected. In 1996, Opatrny et al. [16] introduced the DCC (Disjoint Consecutive Cycle) linear congruential graph, which consists of $n$ nodes and is generated by a set of linear functions $F$ with special properties. In this work, we investigate the strong Menger connectivity of the DCC linear congruential graph ${𝒢}=G_{2t}(F,2^p)$ with faulty vertices or edges, where $2\le t\le p-1,p\ge 5$, $F=\{f_i(x)|f_i(x)=(2^{i-1}b+1)x+2^{i-1}c,1\le i\le t\}$, gcd$(c,2^p)=1$ and $b$ is a multiple of $4$. In detail, we show that ${𝒢}-S$ is strongly Menger connected if $\left|S\right|\le 2t-4$ for any $S\subseteq V({𝒢})$. Moreover, we determine that ${𝒢}-S$ is strongly Menger edge connected if $\left|S\right|\le 2t-2$ for any $S\subseteq E({𝒢})$. Furthermore, we prove that, under the restricted condition $\delta ({𝒢}-S)\ge 2$, ${𝒢}-S$ is strongly Menger edge connected if $\left|S\right|\le 4t-6$ and $t\ge 3$ for any $S\subseteq E({𝒢})$. In addition, we present some empirical examples to show that the bounds are all optimal in the sense of the maximum number of tolerable edge faults.