Fault-Tolerant Hamiltonicity and Hamiltonian Connectivity of BCube with Various Faulty Elements

BCube is one kind of important data center networks. Hamiltonicity and Hamiltonian connectivity have significant applications in communication networks. So far, there have been many results concerning fault-tolerant Hamiltonicity and fault-tolerant Hamiltonian connectivity in some data center networks. However, these results only consider faulty edges and faulty servers. In this paper, we study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity of BCube(n, k) under considering faulty servers, faulty links/edges, and faulty switches. For any integers n ≥ 2 and k ≥ 0, let BC_n,k be the logic structure of BCube(n, k) and F be the union of faulty elements of BC_n,k. Let f_v, f_e, and f_s be the number of faulty servers, faulty edges, and faulty switches of BCube(n, k), respectively. We show that BC_n,k-F is fault-tolerant Hamiltonian if f_v + f_e + (n-1)f_s ≤ (n-1)(k + 1)-2 and BC_n,k-F is fault-tolerant Hamiltonian-connected if f_v + f_e + (n-1)f_s ≤ (n-1)(k + 1)-3. To the best of our knowledge, this paper is the first work which takes faulty switches into account to study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity in data center networks.     

A robustness measure for hypercube networks

Hypercube networks offer a feasible cost-effective solution to parallel computing. Here, a large number of low-cost processors with their own local memories are connected to form an n-cube (B_n) or one of its variants; and the inter-processor communication takes place by message passing instead of shared variables. This paper addresses a constrained two-terminal reliability measure referred to as distance reliability (DR) as it considers the probability that a message can be delivered in optimal time from a given node s to a node t. The problem is equivalent to that of having an operational optimal path (not just any path) between the two nodes. In B_n, the Hamming distance between labels of s and t or H(s, t) determines the length of the optimal path between the two nodes. The shortest distance restriction guarantees optimal communication delay between processors and high link/node utilization across the network. Moreover, it provides a measure for the robustness of symmetric networks. In particular, when H(s, t) = n in B_n, DR will yield the probability of degradation in the diameter, a concept which directly relates to fault-diameter. The paper proposes two schemes to evaluate DR in B_n. The first scheme uses a combinatorial approach by limiting the number of faulty components to (2H(s, t) − 2), while the second outlines paths of length H(s, t) and, then generates a recursive closed-form solution to compute DR. The theoretical results have been verified by simulation. The discrepancy between the theoretical and simulation results is in most cases below 1% and in the worst case 4.6%.     

A sum-of-product neural network (SOPNN)

This paper presents a sum-of-product neural network (SOPNN) structure. The SOPNN can learn to implement static mapping that multilayer neural networks and radial basis function networks normally perform. The output of the neural network has the sum-of-product form ∑Npi=1∏Nvj=1 fij (xj), where xj's are inputs, Nv is the number of inputs, fij( ) is a function generated through network training, and Np is the number of product terms. The function fij(xj) can be expressed as ∑kwijkBjk(xj), where Bjk( ) is a single-variable basis function and Wijk's are weight values. Linear memory arrays can be used to store the weights. If Bjk( ) is a Gaussian function, the new neural network degenerates to a Gaussian function network. This paper focuses on the use of overlapped rectangular pulses as the basis functions. With such basis functions, WijkBjk(xj) will equal either zero or Wijk, and the computation of fij(xj) becomes a simple addition of some retrieved Wijk's. The structure can be viewed as a basis function network with a flexible form for the basis functions. Learning can start with a small set of submodules and have new submodules added when it becomes necessary. The new neural network structure demonstrates excellent learning convergence characteristics and requires small memory space. It has merits over multilayer neural networks, radial basis function networks and CMAC in function approximation and mapping in high-dimensional input space. The technique has been tested for function approximation, prediction of a time series, learning control, and classification.     

Confluent general-factorial difference and derivative operators and polynomial-exponential interpolation

A previous application of the Newton divided difference series of the displacement function E^z = (1 + Δ)^z = e ^Dz, where the operators Δ and D are the variables, to purely exponential interpolation employing general-factorial differences and derivatives, {Pi;^m_i=0 (Δ - S_i)}f(0) and {Pi;^m_i=0 (D - t_i)}f(0), in which the s_i's and t_i's are distinct[1], is here extended to mixed polynomial-exponential interpolation where the s_i's and t_i's are no longer distinct.     

On the error in Padé approximations for functions defined by Stieltjes integrals

Consdier I(z) = ∫^b_a w(t)f(t, z) dt, f(t, z) = (1 + t/z)⁻¹. It is known that generalized Gaussian quadrature of I(z) leads to approximations which occupy the (n, n + r − 1) positions of the Padé matrix table for I(z). Here r is a positive integer or zero. In a previous paper the author developed a series representation for the error in Gaussian quadrature. This approach is now used to study the error in the Padé approximations noted. Three important examples are treated. Two of the examples are generalized to the case where f(t, z) = (1 + t/z)^−v.     

Asymptotic expansions of Hankel transforms of functions with logarithmic singularities

Asymptotic expansions as λ → +∞ are obtained for the Hankel transform

whereJ_v(t) is the Bessel function of the first kind and v is a fixed complex number. The function \tf(t) is allowed to have an asymptotic expansion near the origin of the form

Here, Re _n ↑ +∞ and β_n is an arbitrary complex number.     

Stability of nonlinear time-varying feedback systems

In this paper, the stability of nonlinear time-varying feedback systems is studied using a “passive operator” technique. The feedback system is assumed to consist of a linear time-invariant operator G(s) in the forward path and a nonlinear time-varying gain function f(·)K(t) in the feedback path. The stability condition indicates that the bound on the time derivative [dK(t)/(dt)] depends both on the nonlinearity f(·) and the multiplier Z(s) chosen to make G(s)Z(s) positive real. It is also shown that the main result in this paper can be specialized to yield many of the results obtained so far for nonlinear time-invariant systems and linear time-varying systems.     

A fast algorithm for parametric curve plotting

In parametric curve plotting by means of line segments, a curve r = r(t), t[t₀, t_u] is given, and a set of ordered points r(t_i, iN, t_ie[t₀, t_u] is specified as the vertices of an inscribed polygon of the curve. There are several, analytical, numerical or intuitive ways to derive these vertices obtaining a smooth polygonal approximation. The methods, which can be found in the literature, either belong to some special curves or involve a considerable waste of computing time.

In this paper, we consider an algorithm that appears as a subroutine in the whole program. The subroutine allows the main program to space points as a function of a distance interval for any parametric curve. The design of the routine for performing this spacing is outlined and two examples are shown.     

Least adaptive optimal search with unreliable tests

We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes–no questions, when up to a finite number e of the answers may be erroneous. In case the (i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communication with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let q_e(m) be the smallest integer q satisfying Berlekamp’s bound . Then at least q_e(m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly q_e(m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly q_e(m) questions—or equivalently, e-error correcting codes with 2^m codewords of length q_e(m)—are rather the exception, already for e=2, and are generally not known to exist for e>2. In this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of q_e(m)−m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, q_e(m)−1 questions do not suffice to find the unknown number, and q_e(m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests.     

Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements

A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. We deal with the graph G/sub 0/ /spl oplus/ G/sub 1/ obtained from connecting two graphs G/sub 0/ and G/sub 1/ with n vertices each by n pairwise nonadjacent edges joining vertices in G/sub 0/ and vertices in G/sub 1/. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G/sub 0/ /spl oplus/ G/sub 1/ connecting two lower dimensional networks G/sub 0/ and G/sub 1/. In the presence of faulty vertices and/or edges, we investigate many-to-many disjoint path coverability of G/sub 0/ /spl oplus/ G/sub 1/ and (G/sub 0/ /spl oplus/ G/sub 1/) /spl oplus/ (G/sub 2/ /spl oplus/ G/sub 3/ ), provided some conditions on the Hamiltonicity and disjoint path coverability of each graph G/sub i/ are satisfied, 0 /spl les/ i /spl les/ 3. We apply our main results to recursive circulant G(2/sup m/, 4) and a subclass of hypercube-like interconnection networks, called restricted HL-graphs. The subclasses includes twisted cubes, crossed cubes, multiply twisted cubes, Mobius cubes, Mcubes, and generalized twisted cubes. We show that all these networks of degree m with f or less faulty elements have a many-to-many k-DPC joining any k distinct source-sink pairs for any k /spl ges/ 1 and f /spl ges/ 0 such that f+2k /spl les/ m - 1.     

边故障[k]元[n]立方体的超级哈密顿交织性

[k]元[n]立方体（记为[Qkn]）是优于超立方体的可进行高效信息传输的互连网络之一。[Qkn]是一个二部图当且仅当[k]为偶数。令[G[V0,V1]]是一个二部图,若（1）任意一对分别在不同部的顶点之间存在一条哈密顿路,且（2）对于任意一点[v∈Vi],其中[i∈{0,1}],[V1-i]中任意一对顶点可以被[G[V0,V1]-v]中的一条哈密顿路相连,则图[G[V0,V1]]被称为是超级哈密顿交织的。因为网络中的元件发生故障是不可避免的,所以研究网络的容错性就尤为重要。针对含有边故障的[Qkn],其中[k4]是偶数且[n2],证明了当其故障边数至多为[2n-3]时,该故障[Qkn]是超级哈密顿交织图,且故障边数目的上界[2n-3]是最优的。     

Nonexistence of finite-dimensional filters for conditional statistics of the cubic sensor problem

Consider the cubic sensor dx = dw, dy = x³dt + dv where w, v are two independent Brownian motions. Given a function φ(x) of the state x let φ_t(x) denote the conditional expectation given the observations y_s, 0 s t. This paper consists of a rather detailed discussion and outline of proof of the theorem that for nonconstant φ there cannot exist a recursive finite-dimensional filter for φ driven by the observations.     

A family of Hamiltonian and Hamiltonian connected graphs with fault tolerance

Processor (vertex) faults and link (edge) faults may happen when a network is used, and it is meaningful to consider networks (graphs) with faulty processors and/or links. A k-regular Hamiltonian and Hamiltonian connected graph G is optimal fault-tolerant Hamiltonian and Hamiltonian connected if G remains Hamiltonian after removing at most k?2 vertices and/or edges and remains Hamiltonian connected after removing at most k?3 vertices and/or edges. In this paper, we investigate in constructing optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected graphs. Therefore, some of the generalized hypercubes, twisted-cubes, crossed-cubes, and Möbius cubes are optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected.     

Paired-domination in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained from G by replacing every vertex of degree d of G by a clique K_d. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γ_p(G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ(G)2, then n(G)γ_p(G_I)4m(G)/[δ(G)+1], and the equality γ_p(G_I) = n(G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree.     

Analytic numerical solution of coupled semi-infinite diffusion problems

In this paper, we consider coupled semi-infinite diffusion problems of the form u_t(x, t)− A² u_xx(x,t) = 0, x> 0, t> 0, subject to u(0,t)=B and u(x,0)=0, where A is a matrix in , and u(x,t), and B are vectors in . Using the Fourier sine transform, an explicit exact solution of the problem is proposed. Given an admissible error and a domain D(x₀,t₀)={(x,t);0≤x≤x₀, t≥t₀ > 0, an analytic approximate solution is constructed so that the error with respect to the exact solution is uniformly upper bounded by in D(x₀, t₀).     

An asymptotic theory for recurrence relations based on minimization and maximization

We derive asymptotic approximations for the sequence f(n) defined recursively by f(n)=min_1j<n {f(j)+f(n−j)}+g(n), when the asymptotic behavior of g(n) is known. Our tools are general enough and applicable to another sequence F(n)=max_1j<n {F(j)+F(n−j)+min{g(j),g(n−j)}}, also frequently encountered in divide-and-conquer problems. Applications of our results to algorithms, group testing, dichotomous search, etc. are discussed.     

Fast evaluation of radial basis functions: I

This paper describes some new techniques for the rapid evaluation and fitting of radial basic functions. The techniques are based on the hierarchical and multipole expansions recently introduced by several authors for the calculation of many-body potentials. Consider in particular the N term thin-plate spline, s(x) = Σ_j=1^N d_jφ(x−x_j), where φ(u) = |u|²log|u|, in 2-dimensions. The direct evaluation of s at a single extra point requires an extra O(N) operations. This paper shows that, with judicious use of series expansions, the incremental cost of evaluating s(x) to within precision ε, can be cut to O(1+|log ε|) operations. In particular, if A is the interpolation matrix, a_i,j = φ(x_i−x_j, the technique allows computation of the matrix-vector product Ad in O(N), rather than the previously required O(N²) operations, and using only O(N) storage. Fast, storage-efficient, computation of this matrix-vector product makes pre-conditioned conjugate-gradient methods very attractive as solvers of the interpolation equations, Ad = y, when N is large.     

Conditional Edge-Fault Hamiltonicity of Matching Composition Networks

A graph G is called Hamiltonian if there is a Hamiltonian cycle in G. The conditional edge-fault Hamiltonicity of a Hamiltonian graph G is the largest k such that after removing k faulty edges from G, provided that each node is incident to at least two fault-free edges, the resulting graph contains a Hamiltonian cycle. In this paper, we sketch common properties of a class of networks, called matching composition networks (MCNs), such that the conditional edge-fault hamiltonicity of MCNs can be determined from the found properties. We then apply our technical theorems to determine conditional edge-fault hamiltonicities of several multiprocessor systems, including n-dimensional crossed cubes, n-dimensional twisted cubes, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, and n-dimensional hyper Petersen networks. Moreover, we also demonstrate that our technical theorems can be applied to network construction.     

Properties of the satisfiability threshold of the strictly d-regular random (3, 2s)-SAT problem

A k-CNF (conjunctive normal form) formula is a regular (k, s)-CNF one if every variable occurs s times in the formula, where k≥2 and s>0 are integers. Regular (3, s)- CNF formulas have some good structural properties, so carrying out a probability analysis of the structure for random formulas of this type is easier than conducting such an analysis for random 3-CNF formulas. Some subclasses of the regular (3, s)-CNF formula have also characteristics of intractability that differ from random 3-CNF formulas. For this purpose, we propose strictly d-regular (k, 2s)-CNF formula, which is a regular (k, 2s)-CNF formula for which d≥0 is an even number and each literal occurs s-\frac{d}{2} or s+\frac{d}{2} times (the literals from a variable x are x and \neg x, where x is positive and \neg x is negative). In this paper, we present a new model to generate strictly d-regular random (k, 2s)-CNF formulas, and focus on the strictly d-regular random (3, 2s)-CNF formulas. Let F be a strictly d-regular random (3, 2s)-CNF formula such that 2s>d. We show that there exists a real number s₀ such that the formula F is unsatisfiable with high probability when s>s₀, and present a numerical solution for the real number s₀. The result is supported by simulated experiments, and is consistent with the existing conclusion for the case of d= 0. Furthermore, we have a conjecture: for a given d, the strictly d-regular random (3, 2s)-SAT problem has an SAT-UNSAT (satisfiable-unsatisfiable) phase transition. Our experiments support this conjecture. Finally, our experiments also show that the parameter d is correlated with the intractability of the 3-SAT problem. Therefore, our research maybe helpful for generating random hard instances of the 3-CNF formula.     

Existence of multiple positive solutions for functional differential equations

In this paper, the existence of at least three positive solutions for the boundary value problem (BVP) of second-order functional differential equation with the form y″(t) + f(t, y^t) = 0, for t ε [0,1], y(t) -βy′(t) =η(t), for t ε [−τ,0], −γy(t) + Δy′(t) = ζ(t), for t ε [1, 1 + a], is studied. Moreover, we investigate the existence of at least three partially symmetric positive solutions for the above BVP with Δ = βγ.