Modeling dynamic recovery strategy for composite web services execution

During the execution of Composite Web Services (CWS), a component Web Service (WS) can fail and can be repaired with strategies such WS retry, substitution, compensation, roll-back, replication, or checkpointing. Each strategy behaves differently on different scenarios, impacting the CWS Q o S. We propose a non intrusive dynamic fault tolerant model that analyses several levels of information: environment state, execution state, and Q o S criteria, to dynamically decide the best recovery strategy when a failure occurs. We present an experimental study to evaluate the model and determine the impact on Q o S parameters of different recovery strategies; and evaluate the intrusiveness of our strategy during the normal execution of CWSs.     

Least common container of tree pattern queries and its applications

Tree patterns represent important fragments of XPath. In this paper, we show that some classes \({\mathcal{C}}\) of tree patterns exhibit such a property that, given a finite number of compatible tree patterns \({P_1, \ldots, P_n\in \mathcal{C}}\), there exists another pattern P such that P ₁, . . . , P _n are all contained in P, and for any tree pattern \({Q\in \mathcal{C}}\), P ₁, . . . , P _n are all contained in Q if and only if P is contained in Q. We experimentally demonstrate that the pattern P is usually much smaller than P ₁, . . . , P _n combined together. Using the existence of P above, we show that testing whether a tree pattern, P, is contained in another, \({Q\in \mathcal{C}}\), under an acyclic schema graph G, can be reduced to testing whether P _G , a transformed version of P, is contained in Q without any schema graph, provided that the distinguished node of P is not labeled *. We then show that, under G, the maximal contained rewriting (MCR) of a tree pattern Q using a view V can be found by finding the MCR of Q using V _G without G, when there are no *-nodes on the distinguished path of V and no *-nodes in Q.     

On Some Optimization Problems for the Rényi Divergence

We consider the problem of determining the maximum and minimum of the Rényi divergence D_λ(P||Q) and D_λ(Q||P) for two probability distribution P and Q of discrete random variables X and Y provided that the probability distribution P and the parameter α of α-coupling between X and Y are fixed, i.e., provided that Pr{X = Y } = α.     

Almost cover-free codes

We say that an s-subset of codewords of a code X is (s, l)-bad if X contains l other codewords such that the conjunction of these l words is covered by the disjunction of the words of the s-subset. Otherwise, an s-subset of codewords of X is said to be (s, l)-bad. A binary code X is called a disjunctive (s, l) cover-free (CF) code if X does not contain (s, l)-bad subsets. We consider a probabilistic generalization of (s, l) CF codes: we say that a binary code is an (s, l) almost cover-free (ACF) code if almost all s-subsets of its codewords are (s, l)-good. The most interesting result is the proof of a lower and an upper bound for the capacity of (s, l) ACF codes; the ratio of these bounds tends as s→∞ to the limit value log₂ e/(le).     

On (<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis> )-Distance Anti-Magic and 1-Vertex Bimagic Vertex Labelings of Certain Types of Graphs

The results for the corona P _n ?°?P₁ are generalized, which make it possible to state that P _n ?°?P₁ is not an ( a, d)-distance antimagic graph for arbitrary values of a and d. A condition for the existence of an ( a, d)-distance antimagic labeling of a hypercube Q _n is obtained. Functional dependencies are found that generate this type of labeling for Q _n . It is proved by the method of mathematical induction that Q _n is a (2 ⁿ ?+?n???1,?n???2) -distance antimagic graph. Three types of graphs are defined that do not allow a 1-vertex bimagic vertex labeling. A relation between a distance magic labeling of a regular graph G and a 1-vertex bimagic vertex labeling of G?∪?G is established.     

Some properties of the disjunctive languages contained in <Emphasis Type="Italic">Q</Emphasis>

The set of all primitive words Q over an alphabet X was first defined and studied by Shyr and Thierrin (Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lecture Notes in Computer Science 56. pp. 171–176 (1977)). It showed that for the case |X| ≥ 2, the set along with \({Q^{(i)} = \{f^i\,|\,f \in Q\}, i\geq 2}\) are all disjunctive. Since then these disjunctive sets are often be quoted. Following Shyr and Thierrin showed that the half sets \({Q_{ev} = \{f \in Q\,|\,|f| = {\rm even}\}}\) and Q _od = Q \ Q _ev of Q are disjunctive, Chien proved that each of the set \({Q_{p,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,p) \},\,0\leq r < p}\) is disjunctive, where p is a prime number. In this paper, we generalize this property to that all the languages \({Q_{n,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,n) \},\, 0\leq r < n}\) are disjunctive languages, where n is any positive integer. We proved that for any n ≥ 1, k ≥ 2, (Q _n,0) ^k are all regular languages. Some algebraic properties related to the family of languages {Q _n,r | n ≥ 2, 0 ≤ r < n } are investigated.     

Determining Steady-State Characteristics of Some Queuing Systems with Erlangian Distributions

This article proposes a method to study M / E _s / 1 / m, E _r E _s /1 / m, and E _r / M / n / m queuing systems including the case when m = ∞. Recurrence relations are obtained to compute the stationary distribution of the number of customers in a system and its steady-state characteristics. The developed algorithms are tested on examples using simulation models constructed with the help of the GPSS World tools.     

Reverse Furthest Neighbors Query in Road Networks

Given a road network G = (V,E), where V (E) denotes the set of vertices(edges) in G, a set of points of interest P and a query point q residing in G, the reverse furthest neighbors (Rfn _R ) query in road networks fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in P ∪ {q}. This is the monochromatic Rfn _R (Mrfn _R ) query. Another interesting version of Rfn _R query is the bichromatic reverse furthest neighbor (Brfn _R ) query. Given two sets of points P and Q, and a query point q ∈ Q, a Brfn _R query fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in Q. This paper presents efficient algorithms for both Mrfn _R and Brfn _R queries, which utilize landmarks and partitioning-based techniques. Experiments on real datasets confirm the efficiency and scalability of proposed algorithms.     

Optimal Path Embedding in the Exchanged Crossed Cube

The (s + t + 1)-dimensional exchanged crossed cube, denoted as ECQ(s, t), combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ(s, t) has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ(s, t). We prove the result in ECQ(s, t): if s ≥ 3, t ≥ 3, for any two different vertices, all paths whose lengths are between \( \max \left\{9,\left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +4\right\} \) and 2 ^s+t+1 ? 1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ(s, t) is \( \left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +2 \). The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ(s, t) preserves the path embedding capability to a large extent, while it only has about one half edges of CQ _n .     

Mutually independent Hamiltonian cycles in dual-cubes

The hypercube family Q _n is one of the most well-known interconnection networks in parallel computers. With Q _n , dual-cube networks, denoted by DC _n , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC _n ’s are shown to be superior to Q _n ’s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC _n contains n+1 mutually independent Hamiltonian cycles for n≥2. More specifically, let v _i ∈V(DC _n ) for 0≤i≤|V(DC _n )|?1 and let \(\langle v_{0},v_{1},\ldots ,v_{|V(\mathit{DC}_{n})|-1},v_{0}\rangle\) be a Hamiltonian cycle of DC _n . We prove that DC _n contains n+1 Hamiltonian cycles of the form \(\langle v_{0},v_{1}^{k},\ldots,v_{|V(\mathit{DC}_{n})|-1}^{k},v_{0}\rangle\) for 0≤k≤n, in which v _i ^k ≠v _i ^k′ whenever k≠k′. The result is optimal since each vertex of DC _n has only n+1 neighbors.     

Answering subgraph queries over massive disk resident graphs

Due to its wide applications, subgraph query has attracted lots of attentions in database community. In this paper, we focus on subgraph query over a single large graph G, i.e., finding all embeddings of query Q in G. Different from existing feature-based approaches, we map all edges into a two-dimensional space R ² and propose a bitmap structure to index R ². At run time, we find a set of adjacent edge pairs (AEP) or star-style patterns (SSP) to cover Q. We develop edge join (EJ) algorithms to address both AEP and SSP subqueries. Based on the bitmap index, our method can optimize I/O and CPU cost. More importantly, our index has the linear space complexity instead of exponential complexity in feature-based approaches, which indicates that our index can scale well with respect to large data size. Furthermore, our index has light maintenance overhead, which has not been considered in most of existing work. Extensive experiments show that our method significantly outperforms existing ones in both online and offline processing with respect to query response time, index building time, index size and index maintenance overhead.     

Aggregate location recommendation in dynamic transportation networks

Travel planning and location recommendation are increasingly important in recent years. In this light, we propose and study a novel aggregate location recommendation query (ALRQ) of discovering aggregate locations for multiple travelers and planning the corresponding travel routes in dynamic transportation networks. Assuming the scenario that multiple travelers target the same destination, given a set of travelers’ locations Q, a set of potential aggregate location O, and a departure time t, the ALRQ finds an aggregate location o ∈ O that has the minimum global travel time \({\sum }_{q \in Q} T(q,o,t)\), where T(q,o,t) is the travel time between o and q with departure time t. The ALRQ problem is challenging due to three reasons: (1) how to model the dynamic transportation networks practically, and (2) how to compute ALRQ efficiently. We take two types of dynamic transportation networks into account, and we define a pair of upper and lower bounds to prune the search space effectively. Moreover, a heuristic scheduling strategy is adopted to schedule multiple query sources. Finally, we conducted extensive experiments on real and synthetic spatial data to verify the performance of the developed algorithms.     

Formule di quadratura di tipo gaussiano con valori delle derivate dell'integrando

The coefficientsA _hi (m,s) and the nodesx _i (m,s) for Gaussian-type quadrature formulae

$$\int\limits_{ - 1}^1 {f(x)dx = \mathop \sum \limits_{h = 0}^{2s} \mathop \sum \limits_{i = 1}^m } A_{hi} \cdot f^{(h)} (x_i )$$     

Observational constraints on a hyperbolic potential in brane-world inflation

We focus on the large field of a hyperbolic potential form, which is characterized by a parameter f, in the framework of the brane-world inflation in Randall-Sundrum-II model. From the observed form of the power spectrum P _R (k), the parameter f should be of order 0.1m _p to 0.001m _p , the brane tension must be in the range λ ~ (1?10)×10⁵⁷ GeV⁴, and the energy scale is around V₀ ^1/4 ~ 10¹⁵ GeV. We find that the inflationary parameters (n _s , r, and dn _s /d(ln k) depend only on the number of e-folds N. The compatibility of these parameters with the last Planck measurements is realized with large values of N.     

Discrete Product Inventory Control System with Positive Service Time and Two Operation Modes

Consideration is given to the Markov inventory control system of a discrete product of maximum volume S under the strategies (s,Q) and (s, S) with a positive service time. Upon arrival, the order is queued if the inventory level is positive or, otherwise, leaves the system unserviced. One server handles the queued orders one-by-one in the sequence of their arrival. If the inventory level exceeds s, then the service time has the exponential distribution of intensity μ; otherwise, of intensity αμ, 0 < α ? 1. The product in the inventory is consumed only at the instant when the service (of the order) ends. Inventory deficit is not allowed. When the inventory is empty new orders are not admitted into the system, and the service process of the queued orders (if any) is stopped. The lead time is assumed to be exponentially distributed. Analytical relations are established for the basic stationary performance characteristics of the system.     

Study on microchannel flows with a sudden contraction–expansion at a wide range of Knudsen number using lattice Boltzmann method

Numerical simulations have been performed on the pressure-driven rarefied flow through channels with a sudden contraction–expansion of 2:1:2 using isothermal two and three-dimensional lattice Boltzmann method (LBM). In the LBM, a Bosanquet-type effective viscosity and a modified second-order slip boundary condition are used to account for the rarefaction effect on gas viscosity to cover the slip and transition flow regimes, that is, a wider range of Knudsen number. Firstly, the in-house LBM code is verified by comparing the computed pressure distribution and flow pattern with experimental ones measured by others. The verified code is then used to study the effects of the outlet Knudsen number Kn _o , driving pressure ratio P _i /P _o , and Reynolds number Re, respectively, varied in the ranges of 0.001–1.0, 1.15–5.0, and 0.02–120, on the pressure distributions and flow patterns as well as to document the differences between continuum and rarefied flows. Results are discussed in terms of the distributions of local pressure, Knudsen number, centerline velocity, and Mach number. The variations of flow patterns and vortex length with Kn _o and Re are also documented. Moreover, a critical Knudsen number is identified to be Kn _oc  = 0.1 below and above which the behaviors of nonlinear pressure profile and velocity distribution and the variations of vortex length with Re upstream and downstream of constriction are different from those of continuum flows.     

Resource allocation in cooperative cognitive radio networks towards secure communications for maritime big data systems

In this paper, an innovative framework labeled as cooperative cognitive maritime big data systems (CCMBDSs) on the sea is developed to provide opportunistic channel access and secure communication. A two-phase frame structure is applied to let Secondary users (SUs) entirely utilize the transmission opportunities for a portion of time as the reward by cooperation with Primary users (PUs). Amplify-and-forward (AF) relaying mode is exploited in SU nodes, and Backward induction method based Stackelberg game is employed to achieve optimal determination of SU, power consumption and time portion of cooperation both for non-secure communication scenario and secure communication. Specifically, a jammer-based secure communications scheme is developed to maximize the secure utility of PU, to confront of the situation that the eavesdropper could overheard the signals from SU _i and the jammer. Close-form solutions for the best access time portion as well as the power for SU _i and jammer are derived to realize the Nash Equilibrium. Simulation results validate the effectiveness of our proposed strategy.     

On s-uniform property of compressing sequences derived from primitive sequences modulo odd prime powers

Let Z/(p^e) be the integer residue ring modulo p^e with p an odd prime and e ≥ 2. We consider the suniform property of compressing sequences derived from primitive sequences over Z/(p^e). We give necessary and sufficient conditions for two compressing sequences to be s-uniform with α provided that the compressing map is of the form ?(x₀, x₁,...,x_e?1) = g(x_e?1) + η(x₀, x₁,..., x_e?2), where g(x_e?1) is a permutation polynomial over Z/(p) and η is an (e ? 1)-variable polynomial over Z/(p).     

Organization of self-diagnosis of the discrete multicomponent systems a structure like bipartite quasicomplete graphs

Organization of an efficient self-diagnosis of the multicomponent computer and communication systems of diverse structures always attracted attention of the researchers and engineers. A method to solve these problems is presented in the paper by way of the example of a system whose structure is modeled by a uniform ordinary bipartite graph of diameter d = 3, any degree s > 1, and any number n of vertices, where n = s(s ? 1) + 1. The method requires checking of (s ? 1)³ graph loops of length eight each, which is smaller than the number s ²(s ? 1) + s of checks of single graph edges.     

A polynomial-time algorithm for a flow-shop batching problem with equal-length operations

A flow-shop batching problem with consistent batches is considered in which the processing times of all jobs on each machine are equal to p and all batch set-up times are equal to s. In such a problem, one has to partition the set of jobs into batches and to schedule the batches on each machine. The processing time of a batch B _i is the sum of processing times of operations in B _i and the earliest start of B _i on a machine is the finishing time of B _i on the previous machine plus the set-up time s. Cheng et al. (Naval Research Logistics 47:128–144, 2000) provided an O(n) pseudopolynomial-time algorithm for solving the special case of the problem with two machines. Mosheiov and Oron (European Journal of Operational Research 161:285–291, 2005) developed an algorithm of the same time complexity for the general case with more than two machines. Ng and Kovalyov (Journal of Scheduling 10:353–364, 2007) improved the pseudopolynomial complexity to \(O(\sqrt{n})\). In this paper, we provide a polynomial-time algorithm of time complexity O(log?³ n).