Fault tolerance of hypercubes and folded hypercubes

Let \(G = (V,E)\) be a connected graph. The conditional edge connectivity \(\lambda _\delta ^k(G)\) is the cardinality of the minimum edge cuts, if any, whose deletion disconnects \(G\) and each component of \(G - F\) has \(\delta \ge k\) . We assume that \(F \subseteq E\) is an edge set, \(F\) is called edge extra-cut, if \(G - F\) is not connected and each component of \(G - F\) has more than \(k\) vertices. The edge extraconnectivity \(\lambda _\mathrm{e}^k(G)\) is the cardinality of the minimum edge extra-cuts. In this paper, we study the conditional edge connectivity and edge extraconnectivity of hypercubes and folded hypercubes.     

Some kinds of primitive and non-primitive words

If the length of a primitive word \(p\) is equal to the length of another primitive word \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . This was obtained separately by Tetsuo Moriya in 2008 and Shyr and Yu in 1994. In this paper, we prove that if the length of \(p\) is divisible by the length of \(q\) and the length of \(p\) is less than or equal to \(m\) times the length of \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . Then we show that if \(uv,u\) are non-primitive words and the length of \(u\) is divisible by the length \(v\) or one of the length of \(u\) and \(uv\) is odd for any two nonempty words \(u\) and \(v\) , then \(u\) is a power of \(v\) .     

Isomorphisms and functors of fuzzy sets and cut systems

Any fuzzy set \(X\) in a classical set \(A\) with values in a complete (residuated) lattice \( Q\) can be identified with a system of \(\alpha \) -cuts \(X_{\alpha }\) , \(\alpha \in Q\) . Analogical results were proved for sets with similarity relations with values in \( Q\) (e.g. \( Q\) -sets), which are objects of two special categories \({\mathbf K}={Set}( Q)\) or \({SetR}( Q)\) of \( Q\) -sets, and for fuzzy sets defined as morphisms from an \( Q\) -set into a special \(Q\) -set \(( Q,\leftrightarrow )\) . These fuzzy sets can be defined equivalently as special cut systems \((C_{\alpha })_{\alpha }\) , called f-cuts. This equivalence then represents a natural isomorphism between covariant functor of fuzzy sets \(\mathcal{F}_{\mathbf K}\) and covariant functor of f-cuts \(\mathcal{C}_{\mathbf K}\) . In this paper, we prove that analogical natural isomorphism exists also between contravariant versions of these functors. We are also interested in relationships between sets of fuzzy sets and sets of f-cuts in an \(Q\) -set \((A,\delta )\) in the corresponding categories \({Set}( Q)\) and \({SetR}( Q)\) , which are endowed with binary operations extended either from binary operations in the lattice \(Q\) , or from binary operations defined in a set \(A\) by the generalized Zadeh’s extension principle. We prove that the resulting binary structures are (under some conditions) isomorphic.     

Some properties and algorithms for the hyper-torus network

The hyper-torus network based on a three-dimensional hypercube was introduced recently. The hyper-torus \(QT(m,n)\) performs better than mesh type networks with a similar number of nodes in terms of the network cost. In this paper, we prove that if \(n\) is even, the bisection width of \(QT(m,n)\) is \(6n\) , whereas it is \(6n+2\) if it is odd. Second, we show that \(QT(m,n)\) contains a Hamiltonian cycle. In addition, its one-to-all and all-to-all broadcasting algorithms are introduced. All of these broadcasting algorithms are asymptotically optimal.     

Frequency capping in online advertising

We study the following online problem. There are n advertisers. Each advertiser \(a_i\) has a total demand \(d_i\) and a value \(v_i\) for each supply unit. Supply units arrive one by one in an online fashion, and must be allocated to an agent immediately. Each unit is associated with a user, and each advertiser \(a_i\) is willing to accept no more than \(f_i\) units associated with any single user (the value \(f_i\) is called the frequency cap of advertiser \(a_i\) ). The goal is to design an online allocation algorithm maximizing the total value. We first show a deterministic \(3/4\) -competitiveness upper bound, which holds even when all frequency caps are \(1\) , and all advertisers share identical values and demands. A competitive ratio approaching \(1-1/e\) can be achieved via a reduction to a different model considered by Goel and Mehta (WINE ‘07: Workshop on Internet and Network, Economics: 335–340, 2007). Our main contribution is analyzing two \(3/4\) -competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal integral demand to frequency cap ratios. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the ratio of \(1-1/e\) .     

Growth rates for persistently excited linear systems

We consider a family of linear control systems \(\dot{x}=Ax+\alpha Bu\) on \(\mathbb {R}^d\) , where \(\alpha \) belongs to a given class of persistently exciting signals. We seek maximal \(\alpha \) -uniform stabilization and destabilization by means of linear feedbacks \(u=Kx\) . We extend previous results obtained for bidimensional single-input linear control systems to the general case as follows: if there exists at least one \(K\) such that the Lie algebra generated by \(A\) and \(BK\) is equal to the set of all \(d\times d\) matrices, then the maximal rate of convergence of \((A,B)\) is equal to the maximal rate of divergence of \((-A,-B)\) . We also provide more precise results in the general single-input case, where the above result is obtained under the simpler assumption of controllability of the pair \((A,B)\) .     

A note on the growth factor in Gaussian elimination for accretive-dissipative matrices

This short note proves that if \(A\) is accretive-dissipative, then the growth factor for such \(A\) in Gaussian elimination is less than \(4\) . If \(A\) is a Higham matrix, i.e., the accretive-dissipative matrix \(A\) is complex symmetric, then the growth factor is less than \(2\sqrt{2}\) . The result obtained improves those of George et al. in [Numer. Linear Algebra Appl. 9, 107–114 (2002)] and is one step closer to the final solution of Higham’s conjecture.     

An algebraic axiomatization of the Ewald’s intuitionistic tense logic

Ewald (J Symbolic Logic 51(1):166–179, 1986) considered tense operators \(G\) , \(H\) , \(F\) and \(P\) on intuitionistic propositional calculus and constructed an intuitionistic tense logic system called IKt. The aim of this paper is to give an algebraic axiomatization of the IKt system. We will also show that the algebraic axiomatization given by Chajda (Cent Eur J Math 9(5):1185–1191, 2011) of the tense operators \(P\) and \(F\) in intuitionistic logic is not in accordance with the Halmos definition of existential quantifiers. In this paper, we will study the IKt variety of IKt-algebras. First, we will introduce some examples and we will prove some properties. Next, we will prove that the IKt system has IKt-algebras as algebraic counterpart. We will also describe a discrete duality for IKt-algebras bearing in mind the results indicated by Or?owska and Rewitzky (Fundam Inform 81(1–3):275–295, 2007) for Heyting algebras. We will also get a general construction of tense operators on a complete Heyting algebra, which is a power lattice via the so-called Heyting frame. Finally, we will introduce the notion of tense deductive system which allowed us both to determine the congruence lattice in an IKt-algebra and to characterize simple and subdirectly irreducible algebras of the IKt variety.     

Informational correlation between two parties of a quantum system: spin-1/2 chains

We introduce the informational correlation \(E^{AB}\) between two interacting quantum subsystems \(A\) and \(B\) of a quantum system as the number of arbitrary parameters \(\varphi _i\) of a unitary transformation \(U^A\) (locally performed on the subsystem \(A\) ) which may be detected in the subsystem \(B\) by the local measurements. This quantity indicates whether the state of the subsystem \(B\) may be effected by means of the unitary transformation applied to the subsystem \(A\) . Emphasize that \(E^{AB}\ne E^{BA}\) in general. The informational correlations in systems with tensor product initial states are studied in more details. In particular, it is shown that the informational correlation may be changed by the local unitary transformations of the subsystem \(B\) . However, there is some non-reducible part of \(E^{AB}(t)\) which may not be decreased by any unitary transformation of the subsystem \(B\) at a fixed time instant \(t\) . Two examples of the informational correlations between two parties of the four-node spin-1/2 chain with mixed initial states are studied. The long chains with a single initially excited spin (the pure initial state) are considered as well.     

Budget-bounded model-checking pushdown systems

We address the verification problem for concurrent programs modeled as multi-pushdown systems (MPDS). In general, MPDS are Turing powerful and hence come along with undecidability of all basic decision problems. Because of this, several subclasses of MPDS have been proposed and studied in the literature (Atig et al. in LNCS, Springer, Berlin, 2005; La Torre et al. in LICS, IEEE, 2007; Lange and Lei in Inf Didact 8, 2009; Qadeer and Rehof in TACAS, LNCS, Springer, Berlin, 2005). In this paper, we propose the class of bounded-budget MPDS, which are restricted in the sense that each stack can perform an unbounded number of context switches only if its depth is below a given bound, and a bounded number of context switches otherwise. We show that the reachability problem for this subclass is Pspace-complete and that LTL-model-checking is Exptime-complete. Furthermore, we propose a code-to-code translation that inputs a concurrent program \(P\) and produces a sequential program \(P'\) such that running \(P\) under the budget-bounded restriction yields the same set of reachable states as running \(P'\) . Moreover, detecting (fair) non-terminating executions in \(P\) can be reduced to LTL-Model-Checking of \(P'\) . By leveraging standard sequential analysis tools, we have implemented a prototype tool and applied it on a set of benchmarks, showing the feasibility of our translation.     

Greedy routing in small-world networks with power-law degrees

In this paper we study decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variant of J. Kleinberg’s grid-based small-world model in which (1) the number of long-range edges of each node is not fixed, but is drawn from a power-law probability distribution with exponent parameter \(\alpha \ge 0\) and constant mean, and (2) the long-range edges are considered to be bidirectional for the purposes of routing. This model is motivated by empirical observations indicating that several real networks have degrees that follow a power-law distribution. The measured power-law exponent \(\alpha \) for these networks is often in the range between 2 and 3. For the small-world model we consider, we show that when \(2 < \alpha < 3\) the standard greedy routing algorithm, in which a node forwards the message to its neighbor that is closest to the target in the grid, finishes in an expected number of \(O(\log ^{\alpha -1} n\cdot \log \log n)\) steps, for any source–target pair. This is asymptotically smaller than the \(O(\log ^2 n)\) steps needed in Kleinberg’s original model with the same average degree, and approaches \(O(\log n)\) as \(\alpha \) approaches 2. Further, we show that when \(0\le \alpha < 2\) or \(\alpha \ge 3\) the expected number of steps is \(O(\log ^2 n)\) , while for \(\alpha = 2\) it is \(O(\log ^{4/3} n)\) . We complement these results with lower bounds that match the upper bounds within at most a \(\log \log n\) factor.     

Fault tolerance in distributed systems using fused state machines

Replication is a standard technique for fault tolerance in distributed systems modeled as deterministic finite state machines (DFSMs or machines). To correct \(f\) crash or \(\lfloor f/2 \rfloor \) Byzantine faults among \(n\) different machines, replication requires \(nf\) backup machines. We present a solution called fusion that requires just \(f\) backup machines. First, we build a framework for fault tolerance in DFSMs based on the notion of Hamming distances. We introduce the concept of an ( \(f\) , \(m\) )-fusion, which is a set of \(m\) backup machines that can correct \(f\) crash faults or \(\lfloor f/2 \rfloor \) Byzantine faults among a given set of machines. Second, we present an algorithm to generate an ( \(f\) , \(f\) )-fusion for a given set of machines. We ensure that our backups are efficient in terms of the size of their state and event sets. Third, we use locality sensitive hashing for the detection and correction of faults that incurs almost the same overhead as that for replication. We detect Byzantine faults with time complexity \(O(n f)\) on average while we correct crash and Byzantine faults with time complexity \(O(n \rho f)\) with high probability, where \(\rho \) is the average state reduction achieved by fusion. Finally, our evaluation of fusion on the widely used MCNC’91 benchmarks for DFSMs shows that the average state space savings in fusion (over replication) is 38 % (range 0–99 %). To demonstrate the practical use of fusion, we describe its potential application to two areas: sensor networks and the MapReduce framework. In the case of sensor networks a fusion-based solution can lead to significantly fewer sensor-nodes than a replication-based solution. For the MapReduce framework, fusion can reduce the number of map-tasks compared to replication. Hence, fusion results in considerable savings in state space and other resources such as the power needed to run the backups.     

Query reverse engineering

In this paper, we introduce a new problem termed query reverse engineering (QRE). Given a database \(D\) and a result table \(T\) —the output of some known or unknown query \(Q\) on \(D\) —the goal of QRE is to reverse-engineer a query \(Q'\) such that the output of query \(Q'\) on database \(D\) (denoted by \(Q'(D)\) ) is equal to \(T\) (i.e., \(Q(D)\) ). The QRE problem has useful applications in database usability, data analysis, and data security. In this work, we propose a data-driven approach, TALOS for Tree-based classifier with At Least One Semantics, that is based on a novel dynamic data classification formulation and extend the approach to efficiently support the three key dimensions of the QRE problem: whether the input query is known/unknown, supporting different query fragments, and supporting multiple database versions.     

Parameterized complexity of three edge contraction problems with degree constraints

For any graph class \(\mathcal{H}\) , the \(\mathcal{H}\) -Contraction problem takes as input a graph \(G\) and an integer \(k\) , and asks whether there exists a graph \(H\in \mathcal{H}\) such that \(G\) can be modified into \(H\) using at most \(k\) edge contractions. We study the parameterized complexity of \(\mathcal{H}\) -Contraction for three different classes \(\mathcal{H}\) : the class \(\mathcal{H}_{\le d}\) of graphs with maximum degree at most  \(d\) , the class \(\mathcal{H}_{=d}\) of \(d\) -regular graphs, and the class of \(d\) -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters \(k\) , \(d\) , and \(d+k\) . Moreover, we show that \(\mathcal{H}\) -Contraction admits an \(O(k)\) vertex kernel on connected graphs when \(\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}\) , while the problem is \(\mathsf{W}[2]\) -hard when \(\mathcal{H}\) is the class of \(2\) -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that \(\mathcal{H}\) -Contraction admits a linear vertex kernel when \(\mathcal{H}\) is the class of cycles.     

The categories L-\mathbf{Top}_{0} and L-\mathbf{Sob} as epireflective hulls

We show that the category \(L\) - \(\mathbf{Top}_{0}\) of \(T_{0}\) - \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}\) of \(L\) -topological spaces and the category \(L\) - \(\mathbf{Sob}\) of sober \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}_{0}\) .     

Single-processor scheduling with time restrictions

We consider the following list scheduling problem. We are given a set \(S\) of jobs which are to be scheduled sequentially on a single processor. Each job has an associated processing time which is required for its processing. Given a particular permutation of the jobs in \(S\) , the jobs are processed in that order with each job started as soon as possible, subject only to the following constraint: For a fixed integer \(B \ge 2\) , no unit time interval \([x, x+1)\) is allowed to intersect more than \(B\) jobs for any real \(x\) . It is not surprising that this problem is NP-hard when the value \(B\) is variable (which is typical of many scheduling problems). There are several real world situations for which this restriction is natural. For example, suppose in addition to our jobs being executed sequentially on a single main processor, each job also requires the use of one of \(B\) identical subprocessors during its execution. Each time a job is completed, the subprocessor it was using requires one unit of time in order to reset itself. In this way, it is never possible for more than \(B\) jobs to be worked on during any unit interval. In this paper we carry out a classical worst-case analysis for this situation. In particular, we show that any permutation of the jobs can be processed within a factor of \(2-1/(B-1)\) of the optimum (plus an additional small constant) when \(B \ge 3\) and this factor is best possible. For the case \(B=2\) , the situation is rather different, and in this case the corresponding factor we establish is \(4/3\) (plus an additional small constant), which is also best possible. It is fairly rare that best possible bounds can be obtained for the competitive ratios of list scheduling problems of this general type.     

A Symmetric and Consistent Immersed Finite Element Method for Interface Problems

The non-conforming immersed finite element method (IFEM) developed in Li et al. (Numer Math 96:61–98, 2003) for interface problems is extensively studied in this paper. The non-conforming IFEM is very much like the standard finite element method but with modified basis functions that enforce the natural jump conditions on interface elements. While the non-conforming IFEM is simple and has reasonable accuracy, it is not fully second order accurate due to the discontinuities of the modified basis functions. While the conforming IFEM also developed in Li et al. (Numer Math 96:61–98, 2003) is fully second order accurate, the implementation is more complicated. A new symmetric and consistent IFEM has been developed in this paper. The new method maintains the advantages of the non-conforming IFEM by using the same basis functions but it is symmetric, consistent, and more important, it is second order accurate. The idea is to add some correction terms to the weak form to take into account of the discontinuities in the basis functions. Optimal error estimates are derived for the new symmetric and consistent IFE method in the \(L^2\) and \(H^1\) norms. Numerical examples presented in this paper confirm the theoretical analysis and show that the new developed IFE method has \(O(h^2)\) convergence in the \(L^\infty \) norm as well.     

Quantum teleportation through noisy channels with multi-qubit GHZ states

We investigate two-party quantum teleportation through noisy channels for multi-qubit Greenberger–Horne–Zeilinger (GHZ) states and find which state loses less quantum information in the process. The dynamics of states is described by the master equation with the noisy channels that lead to the quantum channels to be mixed states. We analytically solve the Lindblad equation for \(n\) -qubit GHZ states \(n\in \{4,5,6\}\) where Lindblad operators correspond to the Pauli matrices and describe the decoherence of states. Using the average fidelity, we show that 3GHZ state is more robust than \(n\) GHZ state under most noisy channels. However, \(n\) GHZ state preserves same quantum information with respect to Einstein–Podolsky–Rosen and 3GHZ states where the noise is in \(x\) direction in which the fidelity remains unchanged. We explicitly show that Jung et al.’s conjecture (Phys Rev A 78:012312, 2008), namely “average fidelity with same-axis noisy channels is in general larger than average fidelity with different-axes noisy channels,” is not valid for 3GHZ and 4GHZ states.