Parallel Processing Letters

We present an implementation of an eventually perfect failure detector in an arbitrarily connected, partitionable network. We assume ADD channels: for each one there exist constants $K$, $D$, not known to the processes, such that for every $K$ consecutive messages sent in one direction, at least one is delivered within time $D$. The best previous implementation used messages of bounded size, but exponential in $n$, the number of nodes. The main contribution of this paper is a novel use of time-to-live values in the design of failure detectors, obtaining a flexible implementation that uses messages of size $O(nlogn)$.

In recent years, data are generated rapidly that advanced the evolving of the linked data. Modern data are globally distributed over the semantically linked graphs. The nature of the distributed data over the semantic graph raised new demands on further investigation on improving performance on the semantic graphs. In this work, we analyzed the time latency as an important factor to be further investigated and improved. We evaluated the parallel computing on these distributed data in order to better utilize the parallelism approaches. A federation framework based on a multi-threaded environment supporting federated SPARQL query was introduced. In our experiments, we show the achievability and effectiveness of our model on a set of real-world quires through real-world Linked Open Data cloud. Significant performance improvement has noticed. Further, we highlight short-comings that could open an avenue in the research of federated queries. Keywords: Semantic web; distributed query processing; query federation; linked data; join methods.

In this paper, a parallel algorithm for all nearest smallers problem without using doubly logarithmic tree is described. It is shown that using only $O(loglogn)$ time routines for merging and prefix minima, we can easily get an $O(loglogn)$ time parallel algorithm for the all Nearest Smallers problem.

Let $G=(V(G),E(G))$ be a non-complete graph, a subset $T\subseteq V(G)$ is called a $r$-component cut of $G$, if $G-T$ is disconnected and has at least $r$ components. The cardinality of the minimum $r$-component cut is the $r$-component connectivity of $G$ and is denoted by $c{\kappa }_r(G)$. The $r$-component connectivity is a natural extension of the classical connectivity. As an application, the $r$-component connectivity can be used to evaluate the reliability and fault tolerance of an interconnection network structure based on a graph model. In a previous work, E. Cheng et al. obtained the $r$-component connectivity of the generalized exchanged hypercube $GEH(s,t)$ for $1\le r\le s$ and $s\ge 2$. In this paper, we continue the work and determine that $c{\kappa }_{s+2}(GEH(s,t))=\frac{s^2+3s}{2}-1$ for $s\ge 6$. Moreover, we show that every optimal $r$-component cut of $GEH(s,t)$ is trivial for $1\le r\le s$ and $s\ge 2$.

An edge subset $F$ of $G$ is a fractional matching preclusion set (FMP set for short) if $G-F$ has no fractional perfect matchings. The fractional matching preclusion number (FMP number for short) of $G$, denoted by $fmp(G)$, is the minimum size of FMP sets of $G$. A set $F$ of edges and vertices of $G$ is a fractional strong matching preclusion set (FSMP set for short) if $G-F$ has no fractional perfect matchings. The fractional strong matching preclusion number (FSMP number for short) of $G$, denoted by $fsmp(G)$, is the minimum size of FSMP sets of $G$. Data center networks have been proposed for data centers as a server-centric interconnection network structure, which can support millions of servers with high network capacity by only using commodity switches. In this paper, we obtain the FMP number and the FSMP number for data center networks $D_{n,k}$, and show that $fmp(D_{n,k})=n+k-1$ for $n\ge 2$, $k\ge 0$ and $fsmp(D_{n,k})=n+k-1$ for $n\ge 6$, $k\ge 1$. In addition, all the optimal fractional strong matching preclusion sets of these graphs are categorized.