Narrow Results

A key issue in performing tree structured parallel computations is to distribute process components of a parallel program over processors in a parallel computer at run time such that both the maximum load and dilation are minimized. The main contribution of this paper is the application of recurrence relations in studying the performance of a dynamic tree embedding algorithm in hypercubes. We develop recurrence relations that characterize the expected load in randomized tree embeddings where, a tree grows by letting its nodes to take random walks of short distance. By using these recurrence relations, we are able to calculate the expected load on each processor. Therefore, for constant dilation embeddings, we are able to evaluate expected loads numerically and analytically. The applicability of recurrence relations is due to the recursive structure of trees and the fact that embeddings of the subtrees of a process node are independent of each other. Our methodology does not depend on the hypercube topology. Hence, it can be applied to studying dynamic tree growing in other networks.

In this paper we show the power of sampling techniques in designing efficient distributed algorithms. In particular, we apply sampling techniques in the design of selection algorithms on the hypercube and de Bruijn networks, and show that the message complexity of selecting an item from a set (file) is less sensitive to the cardinality of the set (file). Given a file with n keys, our algorithm performs a selection on a p-node de Bruijn network or hypercube using only O(p loglog n) messages and suffering a delay of O(τ log p loglog n), with high probability. Our selection scheme outperforms the existing approaches in terms of both message complexity and communication delay. Because of the lesser sensitivity of message complexity and communication delay of our algorithms to the file size, our distributed selection schemes are very attractive in applications where very large database systems are involved. Using our selection algorithms, we also show that both quicksort-based sorting scheme and enumeration sorting scheme can be developed for sorting large distributed files on the hypercube and de Bruijn networks. Both of our sorting algorithms outperform the existing distributed sorting schemes in terms of both message complexity and communication delay.

We study hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over a network of processors, and work in a cooperative manner to fulfill various tasks. A hierarchical approach is to group and organize the distributed processes into a logical hierarchy of multiple levels, so as to coordinate the local computation/control activities to improve the overall system performance. It has been proposed as an effective way to solve various problems in distributed computing, such as distributed monitoring, resource scheduling, and network routing. The optimization problem considered in this paper is concerned with finding an optimal hierarchical partition of the processors, so that the total traffic flow over the network is minimized. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting and processing information from all processors. By limiting levels of the hierarchy to two, we will establish the analytically optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed to achieve minimal communication cost (network traffic flow). We will also present and discuss heuristic algorithms for multiple-level hierarchical partitions.

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.

Hypercubes and Fibonacci cubes are classical models for interconnection networks with interesting graph theoretic properties. We consider $k$-Fibonacci cubes, which we obtain as subgraphs of Fibonacci cubes by eliminating certain edges during the fundamental recursion phase of their construction. These graphs have the same number of vertices as Fibonacci cubes, but their edge sets are determined by a parameter $k$. We obtain properties of $k$-Fibonacci cubes including the number of edges, the average degree of a vertex, the degree sequence and the number of hypercubes they contain.

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 multiprocessor systems or multicomputer systems, taking interconnection networks as underlying topologies, have been widely used in the big data era. Fault tolerance is becoming an essential attribute in multiprocessor systems as the number of processors is getting larger. A connected graph $G$ is called strong Menger (edge) connected if, for any two distinct vertices $u$ and $v$, there are $min\{d_G(u),d_G(v)\}$ vertex (edge)-disjoint paths between them. Exchanged hypercube $EH(s,t)$, as a variant of hypercube $Q_n$, remains lots of preferable fault tolerant properties of hypercube. In this paper, we show that $Q_n-Q_k$$(1\le k\le n-1)$ and $EH(s,t)-Q_k$$(2\le k\le min\{s,t\})$ are strong Menger (edge) connected, respectively. Moreover, as a by-product, for dual cube $D_n=EH(n-1,n-1)$, one popular generalization of hypercube, $D_n-Q_k$ is also showed to be strong Menger (edge) connected, where $1\le k\le n-1,n\ge 3$.

We introduce alternate Lucas cubes, a new family of graphs designed as an alternative for the well known Lucas cubes. These interconnection networks are subgraphs of Fibonacci cubes and have a useful fundamental decomposition similar to the one for Fibonacci cubes. The vertices of alternate Lucas cubes are constructed from binary strings that are encodings of Lucas representation of integers. As well as ordinary hypercubes, Fibonacci cubes and Lucas cubes, alternate Lucas cubes have several interesting structural and enumerative properties. In this paper we study some of these properties. Specifically, we give the fundamental decomposition giving the recursive structure, determine the number of edges, number of vertices by weight, the distribution of the degrees; as well as the properties of induced hypercubes, $q$-cube polynomials and maximal hypercube polynomials. We also obtain the irregularity polynomials of this family of graphs, determine the conditions for Hamiltonicity, and calculate metric properties such as the radius, diameter, and the center.

This paper analyses how the symmetry of a processor network influences the existence of a solution for the network orientation problem. The orientation of hypercubes and tori is the problem of assigning labels to each link of each processor, in such a way that a sense of direction is given to the network. In this paper the problem of network orientation for these two topologies is studied under the assumption that the network contains a single leader, under the assumption that the processors possess unique identities, and under the assumption that the network is anonymous. The distinction between these three models is considered fundamental in distributed computing.

It is shown that orientations can be computed by deterministic algorithms only when either a leader or unique identities are available. Orientations can be computed for anonymous networks by randomized algorithms, but only when the number of processors is known. When the number of processors is not known, even randomized algorithms cannot compute orientations for anonymous processor networks.

Lower bounds on the message complexity of orientation and algorithms achieving these bounds are given.

The hypercube as a parallel interconnection network has been of academic and engineering concern for tens of year due to its many merits. However, its increasing node degree is an obvious weakness. Some networks such as the cube-connected cycles (CCC) and the de Bruijn network have been proposed to overcome the increasing degree of the hypercube. In this paper, we present a new cost-effective network which outperforms the cube network. It can overcome the increasing degree of cube networks while keeping the advantages of the cube network such as logarithmic diameter, easy routing, optimal fault tolerance, and suitability for the ASCEND/DESCEND class of parallel problems. Furthermore, the proposed network achieves the logarithmic diameter with a very small constant node degree, 3 or 4.

Given a shortest path routing algorithm of an interconnection network, the edge congestion is one of the important factors to evaluate the performance of this algorithm. In this paper, we consider the twisted cube, a variation of the hypercube with some better properties, and review the existing shortest path routing algorithm⁸. We find that its edge congestion under the routing algorithm is high. Then, we propose a new shortest path routing algorithm and show that our algorithm has optimum time complexity O(n) and optimum edge congestion 2ⁿ. Moreover, we calculate the bisection width of the twisted cube of dimension n.

We consider routing in hypercube networks with a very large number (i.e., up to a constant fraction) of faulty nodes. Simple and natural conditions are identified under which hypercube networks with a very large number of faulty nodes still remain connected. The conditions can be detected and maintained in a distributed manner based on localized management. Efficient routing algorithms on hypercube networks satisfying these conditions are developed. For a hypercube network that satisfies the conditions and may contain up of 37.5% faulty nodes, our algorithms run in linear time and for any two given non-faulty nodes find a routing path of length bounded by four times the Hamming distance between the two nodes. Moreover, our algorithms are distributed and local-information-based in the sense that each node in the network knows only its neighbors' status and no global information of the network is required by the algorithms.

Index-shuffle graphs are a family of bounded-degree hypercube-like interconnection networks for parallel computers, introduced by [Baumslag and Obrenić (1997): Index-Shuffle Graphs, …], as an efficient substitute for two standard families of hypercube derivatives: butterflies and shuffle-exchange graphs. In the theoretical framework of graph embedding and network emulations, this paper shows that the index-shuffle graph efficiently approximates the direct-product structure of the hypercube, and thereby has a unique potential to approximate efficiently all of its derivatives.

One of the consequences of our results is that any member of the following group of standard bounded-degree hypercube derivatives: butterflies, shuffles, tori, meshes of trees, is emulated by the index-shuffle graph with a slowdown in the order of the logarithm of the slowdown of the most efficient emulation achieved by any other member of this group.

Emulation algorithms are presented where the emulation host is the n-dimensional index-shuffle graph Ψ_n, having N=2ⁿ nodes. The emulated graph G is a direct product of the form: G=F₀×F₁×⋯×F_k-1 where k is a power of 2, and each factor F_i is an instance of any of the following three graph families: cycle, complete binary tree, X-tree. Let the size of each factor be |F_i|≤2^n_f, where k·n_f≤n. The index-shuffle graph Ψ_n, emulates any factor F_i in the product G with slowdown: O(log k) + O(log n_f), which is O(log n) = O(loglog N). Any collection of 2^ℓ copies of the product G, such that: ℓ+k·n_f≤n is emulated by the index-shuffle graph Ψ_n simultaneously, without any additional slowdown. Relaxing the assumption that k is a power of 2 introduces an additional factor of O(lg*N) into the slowdown.

Extensive experiments and experience have shown that the well-known hypercube networks are highly fault tolerant. What is frustrating is that it seems very difficult to properly formulate and formally prove this important fact, despite extensive research efforts in the past two decades. Most proposed fault tolerance models for hypercube networks are only able to characterize very rare extreme situations thus significantly underestimating the fault tolerance power of hypercube networks, while for more realistic fault tolerance models, the analysis becomes much more complicated. In this paper, we develop new techniques that enable us to analyze a more realistic fault tolerance model and derive lower bounds for the probability of hypercube network fault tolerance in terms of node failure probability. Our results are both theoretically significant and practically important. From the theoretical point of view, our method offers very general and powerful techniques for formally proving lower bounds on the probability of network connectivity, while from the practical point of view, our results provide formally proven and precisely given upper bounds on node failure probabilities for manufacturers to achieve a desired probability for network connectivity. Our techniques are also useful and powerful for analysis of the performance of routing algorithms, and applicable to the study of other hierarchical network structures and to other network communication problems.

Two hamiltonian paths P₁ = 〈v₁, v₂, …, v_n(G) 〉 and P₂ = 〈 u₁, u₂, …, u_n(G) 〉 of G are independent if v₁ = u₁, v_n(G) = u_n(G), and v_i ≠ u_i for 1 < i < n(G). A set of hamiltonian paths {P₁, P₂, …, P_k} of G are mutually independent if any two different hamiltonian paths in the set are independent. A bipartite graph G is hamiltonian laceable if there exists a hamiltonian path joining any two nodes from different partite sets. A bipartite graph is k-mutually independent hamiltonian laceable if there exist k-mutually independent hamiltonian paths between any two nodes from different partite sets. The mutually independent hamiltonian laceability of bipartite graph G, IHP_L(G), is the maximum integer k such that G is k-mutually independent hamiltonian laceable. Let Q_n be the n-dimensional hypercube. We prove that IHP_L(Q_n) = 1 if n ∈ {1,2,3}, and IHP_L(Q_n) = n - 1 if n ≥ 4. A hamiltonian cycle C of G is described as 〈 u₁, u₂, …, u_n(G), u₁ 〉 to emphasize the order of nodes in C. Thus, u₁ is the beginning node and u_i is the i-th node in C. Two hamiltonian cycles of G beginning at u, C₁ = 〈 v₁, v₂, …, v_n(G), v₁ 〉 and C₂ = 〈 u₁, u₂, …, u_n(G), u₁ 〉, are independent if u = v₁ = u₁, and v_i ≠ u_i for 1 < i ≤ n(G). A set of hamiltonian cycles {C₁, C₂, …, C_k} of G are mutually independent if any two different hamiltonian cycles are independent. The mutually independent hamiltonianicity of graph G, IHC(G), is the maximum integer k such that for any node u of G there exist k-mutually independent hamiltonian cycles of G starting at u. We prove that IHC(Q_n) = n - 1 if n ∈ {1,2,3} and IHC(Q_n) = n if n ≥ 4.

Current studies of "messy" broadcasting have so far concentrated on finding worst-case times. However, such worst-case scenarios are extremely unlikely to occur in general. Hence, determining average-case times or tight upper bounds for completing "messy" broadcasting in various network topologies is both necessary and meaningful in practice. In this paper, we focus on seeking the average-case "messy" broadcast times of stars, paths, cycles, and d-ary trees, and finding good upper bounds for hypercubes. Finally, we derive a recursive formula to express the average-case time for a specific "messy" broadcast model on a complete graph using a classical occupancy problem in probability theory, and provide a nice simulation result which indicates that this model behaves like classical broadcasting.

In this paper we study the fault diameter of the n-dimensional hypercube (or n-cube for short), Q_n, for n ≥ 3. Let F be a set of hybrid node-faults and/or link-faults in Q_n such that every node of Q_n is still connected to at least one fault-free node by a fault-free link. Then we compute the exact diameter of Q_n - F for |F| ≤ 2n - 3. As an immediate consequence, our result improves upon those presented by S. Latifi (1993), in which only node-faults were addressed.

Assume that n is a positive integer with n ≥ 4 and F is a subset of the edges of the hypercube Q_n with |F| ≤ n-4. Let u, x be two distinct white vertices of Q_n and v, y be two distinct black vertices of Q_n, where black and white refer to the two parts of the bipartition of Q_n. Let l₁ and l₂ be odd integers, where l₁ ≥ d_Qn-F(u, v), l₂ ≥ d_Qn-F(x,y), and l₁ + l₂ = 2ⁿ - 2. Moreover, let l₃ and l₄ be even integers, where l₃ ≥ d_Qn-F(u,x), l₄ ≥ d_Qn-F(v,y), and l₃+l₄ = 2ⁿ - 2. In this paper, we prove that there are two disjoint paths P₁ and P₂ such that (1) P₁ is a path joining u to v with length l(P₁) = l₁, (2) P₂ is a path joining x to y with l(P₂) = l₂, and (3) P₁ ∪ P₂ spans Q_n - F. Moreover, there are two disjoint paths P₃ and P₄ such that (1) P₃ is a path joining u to x with l(P₃) = l₃, (2) P₄ is a path joining v to y with l(P₄) = l₄, and (3) P₃ ∪ P₄ spans Q_n - F except the following cases: (a) l₃ = 2 with d_Qn-F(u,x) = 2 and d_Qn-F-{v,y}(u,x) > 2, and (b) l₄ = 2 with d_Qn-F(v,y) = 2 and d_Qn-F-{u,x}(v,y) > 2.

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.

The hypercube is one of the most popular interconnection networks due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance. In this paper, we introduce a tree called l-sibling trees and the main results obtained in this paper are: (1) For r ≥ 1, the minimum wirelength of embedding r-dimensional hypercube into r-dimensional l-sibling tree. (2) For r ≥ 1, embedding of r-dimensional extended l-sibling tree into caterpillar with minimum dilation. (3) Based on the proof of (1), we provide an O(r)-linear time algorithm to compute the minimum wirelength of embedding r-dimensional hypercube into r-dimensional l-sibling tree.