In the realm of interconnection networks, reliability analysis is of utmost importance, especially considering the increasing vulnerability of components as the network scales. Fault tolerance is a key aspect in this regard, and extra connectivity and component connectivity are two crucial metrics for its assessment. In this paper, we establish a theoretical framework for multi-component fault tolerance in the augmentedk-aryn-cubeAQn,k, a hypercube-derived interconnection network commonly used in distributed-memory architectures. We derive a general result for ther-component connectivity ofAQn,kas$4n(n - 1) - \lfloor{\frac{{5{{(r - 1)}^2}}}{2}}\rfloor$(n≥ 4,k≥ 4, and 2 ≤r≤n). Furthermore, we extend the result to explore theh-extrar-component connectivity ofAQn,kas (8n− 10)(r−1) −2(r−2) (n≥ 4,k≥ 4,h= 1 and 2≤r≤n). Based on these theoretical results, we propose a novel fault-tolerant path algorithm forAQn,kthat handlesh-extrar-component faults. The algorithm first preprocesses and classifies fault-free components, which efficiently determines whether two fault-free nodes belong to the same component, thereby avoiding ineffective path searches. When two fault-free nodes are in the same component, we employ a hybrid greedy-BFS algorithm to construct fault-free paths between them. To validate the algorithm, we conduct comprehensive simulations onAQn,kwith varying parameters. The experimental results demonstrate that the proposed algorithm achieves constant-time path existence queries after preprocessing, significantly reduces path discovery time in multi-query scenarios compared to conventional methods, and maintains near-optimal path lengths while exhibiting superior scalability as network dimensions increase. Furthermore, the algorithm demonstrates robust and highly efficient performance even under fault conditions significantly exceeding theoretical connectivity limits. Additionally, the greedy strategy effectively resolves the vast majority of pathfinding scenarios, confirming its effectiveness underh-extrar-component fault conditions.

Fault diagnosis is crucial for ensuring the reliability of interconnection networks. Traditional diagnostic models usually assume that edges connected to faulty nodes are fault-free, which is unrealistic in practice where both node and edge failures can occur simultaneously. The recently proposed HPMC* diagnostic model provides a more realistic framework by considering both node and edge failures simultaneously, but existing diagnostic approaches under this model have significant limitations in handling complex fault scenarios. This paper proposes HYBRID-GNN, the first graph neural network-based approach for hybrid fault diagnosis under the HPMC* model. HYBRID-GNN employs an edge-enhanced GraphSAGE with comprehensive feature engineering that extracts diagnostic characteristics from HPMC* syndrome data and enables joint training for node and edge fault prediction. HYBRID-GNN learns complex fault patterns from syndrome data, overcoming traditional diagnosability constraints. Experiments on multiple interconnection network topologies show that HYBRID-GNN matches the traditional algorithm in node fault diagnosis (achieving over 99% accuracy within the hybrid diagnosability bound), while delivering substantially higher performance in link fault diagnosis (with accuracy above 97%). Even beyond the diagnosability bound, HYBRID-GNN remains robust, maintaining over 98% node accuracy and over 83% link precision under high fault rates. Furthermore, results on real-world networks further validate its practical effectiveness, achieving over 99% node accuracy and over 95% link accuracy.

Given a simple undirected graph$G$, a set of spanning trees for$G$are completely independent spanning trees (CISTs for short), where for any two vertices$x, y \in V(G)$, the paths connecting$x$and$y$on these trees have no common vertices and edges except$x$and$y$. In this paper, we provide an approach to construct three CISTs in three$n$-dimensional folded hypercube-variant networks, including enhanced hypercubes ($n=5$), folded crossed cubes ($n=5$) and complete Josephus cubes ($n=4$). For higher-dimensional networks, we propose a recursive algorithm that generates three CISTs with diameters of order$2 n+c$for some constant$c$. Finally, we simulate numerous node pairs using the three constructed CISTs to configure protection routes, test random node failures, and employ the transmission failure rate (TFR) to evaluate the effectiveness of CIST-based protection routing, demonstrating strong fault tolerance under various failure scenarios.

A network can contain numerous spanning trees. If two spanning trees T i , T j do not share any common edges, T i and T j are said to be pairwisely edge-disjoint. For spanning trees T 1 , T 2 ,…, T m , if every two of them are pairwisely edge-disjoint, they are called completely edge-independent spanning trees (CEISTs for short). CEISTs can facilitate many network functionalities, and constructing CEISTs as maximally allowed as possible in a given network is a worthy undertaking. In this paper, we establish the maximal number of CEISTs in the locally twisted cube network, and propose an algorithm to construct ⌊ n 2 ⌋ CEISTs in LTQ n , the n -dimensional locally twisted cube. The proposed algorithm has been actually implemented, and we present the outputs. Network broadcasting in the LTQ n was simulated using ⌊ n 2 ⌋ CEISTs, and the performance compared with broadcasting using a single tree.

It is widely known that parallel and distributed systems are crucial technologies and platforms necessary to support supercomputing and cloud computing. The network architecture forms the foundational support for the stable operation of these systems, directly influencing their reliability, scalability, and robustness. As the network scale expands, the probability of processor/server and communication link failures increases. Therefore, it is imminent to consider how to build up the fault tolerance and reliability of the network. The circulant-based recursive networks (CRNs) are a novel type of network with several desirable properties such as regularity, recursiveness, vertex (edge) transitivity and so on. CRNs contain not only interconnection networks hypercubes and$k$-ary$n$-cubes, but also data center network BCube, as well as some future networks. Connectivity and diagnosability of networks have garnered significant attention, as they suffice for analyzing and measuring networks' fault tolerance. This article focuses primarily on conditional connectivity and diagnosability under the good neighbor fault pattern. In this work, we explore the conditional connectivity and diagnosability (built on$g$-good neighbor fault pattern) of the$f$-dimensional$r$-order CRN under the PMC model and MM* model, respectively. These values are nearly$g$times greater than the traditional connectivity and diagnosability of CRNs, respectively, implying that they can further improve fault tolerance of CRNs. Furthermore, it is worth noting that the results can be effectively utilized in BCube and other future networks given that they are both subclasses of CRNs.

With the increasing network scale, hardware faults are inevitable. Therefore, research on network reliability under the condition of hardware failure is an important subject. In this article, we investigate$h$-extra connectivity,$h$-extra diagnosability under the PMC and MM$^{*}$models, and$t/m$-diagnosability under the PMC model of recursive networks based on complete graphs (RNCGs) that include not only interconnection network Dragonfly but also data center networks—DCell, generalized DCell, and other unknown networks. In addition, we propose the fault-tolerant routing (F-TR) algorithm, FTPath, which constructs a F-TR in the largest component when the number of faulty nodes is less than the$h$-extra connectivity. Moreover, we evaluate the performance of RNCGs. First, we compare the fault-tolerant performance of RNCGs through experiments. The results show that the average path length constructed by the FTPath algorithm is close to that of the breadth-first search algorithm, and shorter than that of the depth-first search algorithm. Second, we evaluate the performance of this network for different parameters:$h$-extra connectivity, diagnosability under different strategies. The results show that the network has good fault tolerance and fault diagnosis capabilities.

Abstract Fault-tolerant performance of a network is the prerequisite and guarantee for the normal operation of a network, which is often characterized by connectivity. Let $H$ denote a connected subgraph of $G$ and $H^{*}$ denote the union of the set of all connected subgraphs of $H$ and the set of the trivial graph. Super $H$-connectivity (resp. super $H^{*}$-connectivity) satisfies the conditions of both super connectivity and $H$-structure connectivity (resp. $H$-substructure connectivity). These two kinds of new connectivity provide a new metric to measure the fault-tolerance of the network, that is, the super structure fault-tolerance. The generalized hypercube $G(m_{r}, m_{r-1},..., m_{1})$ is a universal topology of interconnection networks that contains other commonly used topologies and it has been applied in many data center networks because of its excellent qualities. In this paper, we research the super structure fault-tolerance of $G(m_{r}, m_{r-1},..., m_{1})$ by studying super $H$-connectivity $\kappa ^{\prime}(G|H)$ and super $H^{*}$-connectivity $\kappa ^{\prime}(G|H^{*})$ for $H\in \{K_{1,M},\ C_{3},\ C_{4},\ K_{4}\}$.

Abstract According to Menger’s theorem, connectivity and edge connectivity are closely related to node-disjoint paths and edge-disjoint paths, respectively. Node- and edge-disjoint paths can keep the effective transmission of information and confidentiality. Therefore, node-disjoint paths and edge-disjoint paths are two important parameters to measure the reliability of a network. For a faulty node (resp. edge) set $S\subset V$ (resp. $S\subset E$), a connected graph $G=(V,E)$ is $S$-strongly Menger-node-connected (resp. Menger-edge-connected) if any two distinct nodes $x$ and $y$ in $G-S$ are connected by $\min \{\deg _{G-S}(x),\deg _{G-S}(y)\}$ internally node-disjoint (resp. edge-disjoint) paths in $G-S$, where $\deg _{G-S}(x)$ and $\deg _{G-S}(y)$ are the degrees of $x$ and $y$ in $G-S$, respectively. And most of the previous studies are based on networks that are triangle-free. In this paper, we consider the strongly Menger (edge) connectedness of a class of $r$-dimensional recursive networks RNCG $G_{r}$ with triangles. Moreover, we show that $G_{r}$ is $(rl-l-1)$-strongly Menger-node-connected. And then we show that $G_{r}$ is $[k+(r-1)l-2]$-strongly Menger-edge-connected of order 1 and $[2k+2(r-1)l-6]$-strongly Menger-edge-connected of order 2. Since the class of $r$-dimensional recursive networks RNCG $G_{r}$ includes not only data center networks DCell and generalized DCell but also interconnection network dragonfly, etc., all the results are appropriate for these networks.

Competitive influence maximization (CIM) has been studied for years due to its wide application in many domains. Most current studies primarily focus on the microlevel optimization by designing policies for one competitor to defeat its opponents. Furthermore, current studies ignore the fact that many influential nodes have their own starting prices, which may lead to inefficient budget allocation. In this article, we propose a novel competitive bidding influence maximization (CBIM) problem, where the competitors allocate budgets to bid for the seeds attributed to the platform during multiple bidding rounds. To solve the CBIM problem, we propose a fairness-aware multiagent CBIM (FMCBIM) framework. In this framework, we present a multiagent bidding particle environment (MBE) to model the competitors’ interactions and design a starting price adjustment mechanism to model the dynamic bidding environment. Moreover, we put forward a novel multiagent CBIM (MCBIM) algorithm to optimize competitors’ bidding policies. Extensive experiments on five datasets show that our work has good efficiency and effectiveness.

Networks of large scales are an essential component in supercomputing systems as well as in data centers. As the network scale increases, the probability of processor/server failures also inevitably increases. It is therefore a worthwhile undertaking to make efforts reducing, as much as possible, the effect of faulty processors/servers to the entire network. This paper introduces a new class of network architectures, called circulant-based recursive networks (CRNs), and investigates CRN’s diameter, connectivity, and in particular, the fault diagnosability under the two diagnostic models−the PMC and the comparison diagnostic models. CRNs are a generalization of some well-known interconnection networks−hypercube, k-ary n-cube network and the data center network BCube, as well as some other less-known networks. In addition to obtaining its diagnosability properties, the paper also presents a one-to-one (unicast) path construction algorithm named SPath. Based on SPath, we further propose an algorithm FTPath for CRNs finding a fault-tolerant path between any two vertices, provided that the number of faulty vertices is no more than its connectivity minus one. Three parameters−average distance, message density, and cost−are used to assess CRNs’ performance. Experimental comparisons are conducted, and the results indicate that the average path length obtained by the algorithm SPath (resp., FTPath) is shorter than that of the Depth-First Search algorithm (DFS) and is on a par with the Breath-First Search algorithm (BFS).

Most data center services are finished by the cooperation among the connected servers. However, the malicious attackers always try to divide the network into disconnected components to start some attacks, such as the address resolution protocol (ARP) attack, the denial of service (DoS) attack, the botnet attack, and so on. The connectivity is an excellent indicator to measure the reliability and fault-tolerant ability of the network. Whereas, the traditional connectivity and current conditional connectivity cannot well reflect the fault-tolerant performance of the network when attackers are a block or have a certain structure and the components of the remaining network still have a certain structure. Based on this fact, we propose a new measure: the double-structure connectivity, which can accurately reflect the fault-tolerant ability of the network when attackers are structured and each component of the network has a certain structure after removing the attacked servers. Meanwhile, a hypercube is a high-performance interconnection network that can also be used to design some data center networks. Therefore, we study the double-structure fault-tolerance of the hypercube and determine the double-structure connectivity of distinct structures of the hypercube. Furthermore, we propose algorithms to construct structures of attackers directly to measure the fault-tolerant ability of the hypercube under this attack. Our results can be applied not only to interconnection networks but also to some data center networks.

Topology design is vital to the high performance data center networks. Due to the limited scalability, many traditional server-centric data center networks are confronting the updating and upgrading hurdles. To address the issue, this paper proposes a highly scalable DCell-based server-centric data center network topology, called HS-DCell, which can use inexpensive and typical switches and servers with only three network ports to achieve excellent network performance HS-DCell can accommodate a large number of servers, and its diameter increases linearly with the growth of network levels, which is better than that of most existing server-centric networks. Furthermore, a fault-free routing algorithm and a fault-tolerant routing algorithm are developed based on HS-DCell. Compared with other mainstream server-centric network topologies, the experimental results show that HS-DCell has obvious advantages in many key performance indicators including scalability, fault tolerance, and server port utilization.

One of the important issues in evaluating an interconnection network is to study the fault-tolerant Hamiltonian cycle and Hamiltonian path embedding problems. The$k$-ary$n$-cube (denoted by$Q^{k}_{n}$) networks are used as interconnection networks for many parallel and distributed computing systems. In this article, we investigate the Hamiltonian cycle and path embeddings in the bipartite$k$-ary$n$-cube$Q^{k}_{n}$based on$K_{1,1}$-structure faults. We show that there exists a Hamiltonian cycle in$Q^{k}_{n}-\mathcal {F}$if$|\mathcal {F}|\leq 2n-2$and there exists a Hamiltonian path between any two vertices from different partite sets in$Q^{k}_{n}-\mathcal {F}$if$|\mathcal {F}|\leq 2n-3$for$n\geq 2$and even$k\geq 4$, where$\mathcal {F}$is a set of vertex-disjoint subgraphs isomorphic to$K_{1,1}$in$Q_{n}^{k}$. In some sense, the results mean that when a subset$S$of at most$4n-4$(resp.$4n-6$) processors is deleted from a bipartite$Q^{k}_{n}$, there exists a Hamiltonian cycle (resp. a Hamiltonian path between any two healthy processors from different partite sets) in the remaining network. Our results, in some sense, compensate the results in Lv et al. [J. Parallel Distrib. Comput., 120, 148–158, 2018] and [Comput. J., 60, 159–179, 2017], where authors studied the$K_{1,3}$-substructure fault-tolerant Hamiltonian cycle and path embedding problems in nonbipartite$k$-ary$n$-cubes. In comparison, the bipartite$k$-ary$n$-cube$Q^{k}_{n}$can keep the same$K_{1,1}$-structure fault-tolerant Hamiltonian capabilities as the nonbipartite one.

The efficiency of cloud computing is significantly impacted by the capabilities of data center networks (DCNs). However, with the increasing demands of applications, the number of servers in DCNs is growing exponentially. In general, networks become more vulnerable as they expand in size. Consequently, it is essential to assess the network's reliability. Subsystem reliability, a crucial parameter of network reliability, is the likelihood that a faultless subsystem with a specific size would function normally. Even though several networks have the same order, their subsystem reliability may differ. In this article, we compare two distinct subsystems of$m$-port$k$-dimensional DCNs BCube that have the same number of vertices and ascertain the critical time so that the reliability bound is robust. In addition, we discover that, when comparing two subsystems of BCube that have the same number of vertices, the smaller the dimension$k$, the greater the subsystem reliability of BCube will be for$m\geq 2$and$k\geq 1$. This offers a theoretical foundation that allows us to choose a more reliable system in BCube that have the same number of vertices. Finally, we use numerical experiments to verify our findings.

Abstract The data center network HSDC is a superior candidate for building large-scale data centers, and strikes a good balance among diameter, bisection width, incremental scalability and other important characteristics in contrast to the state-of-the-art data center network architectures. The Hamiltonian property is an important indicator to measure the reliability of a network. In this paper, we study the Hamiltonian properties of HSDC’s logic graph $H_n$. Firstly, we prove that $H_n$ is Hamiltonian-connected for $n\geq 3$. Secondly, we propose an $O(NlogN)$ algorithm for finding a Hamiltonian path between any two distinct nodes in $H_n$, where $N$ is the number of nodes in $H_n$. Furthermore, we consider the Hamiltonian properties of $H_n$ with faulty elements, and prove that $H_n$ is $(n-3)$-fault-tolerant Hamiltonian-connected and $(n-2)$-fault-tolerant Hamiltonian for $n\geq 3$.

Abstract As a kind of conditional connectivity, component connectivity is an improvement of traditional connectivity, which is conducive to enhance the reliability of the network. To be specific, the $r$-component connectivity of a network $G$, written as $c\kappa _{r}(G)$, is defined as the minimum number of all node cuts whose removal causes the remaining network to have at least $r$ components. Component diagnosability, as another measure of network reliability, is usually related to the number of components in the remaining network. The $r$-component diagnosability, written as $ct_{r}(G)$, is defined as the maximum number of faulty sets such that at least $r$ components in the surviving network and all faulty nodes can be diagnosed. This paper mainly explores the relationship between component connectivity and component diagnosability of some regular networks. Once knowing the component connectivity of such a network, with the help of this relationship, we can easily obtain the component diagnosability of the network. Furthermore, we apply this relationship to some famous regular networks to obtain their component diagnosabilities under the PMC model.

With the increasing scale of parallel computer interconnection network, the possibility of processor failure or link failure between processors in the network is also increasing. In the design of supercomputers, not only link overhead and communication delay should be taken into account, but also fault-tolerant performance of networks should be emphasized. Locally exchanged twisted cube ($LeTQ$) is a newly proposed interconnection network with lower link overhead and shorter diameter. With the increasing scale of supercomputers, fault-tolerant routing is indispensable. In this article, we propose a new load balancing fault-tolerant routing algorithm based on node contraction for$LeTQ$networks. The proposed algorithm uses the node shrinkage method to evaluate the priority of nodes. The sending node adaptively adjusts the probability of forwarding packets to the neighbor node according to the priority of the neighbor node and the state of the network. The path can be adapted to the load state of the network. The simulation results show that the fault-tolerant routing algorithm has good performance in throughput and delay.

With the continuous attention to the parallel computing system, the reliability of the system, which is mainly measured by two parameters, connectivity and diagnosability, needs to be constantly studied and improved. At present, the component connectivities of some networks have been extensively studied, while the component diagnosabilities of these networks have rarely involved in. In this article, some networks with common characteristics are summarized as a class of regular networks. The definition of this kind of networks is given, and its reliability based on component failures is determined. To be specific, we prove that$c\kappa _{m+1}(G)=m(k-1)-\binom{m}{2}+1$for$1\leq m\leq k-2$and$ct_{m+1}(G)=(m+1)k-\binom{m}{2}-2\ m$for$1\leq m\leq k-2$under the PMC model, where$c\kappa _{m+1}(G)$and$ct_{m+1}(G)$represent the$(m+1)$-component connectivity and the$(m+1)$-component diagnosability of such networks$G$, respectively. Based on this, we design a low time complexity component diagnosis algorithm for this kind of networks. As applications, the above two component reliability parameters of many famous networks are explored. Furthermore, the proposed diagnosis algorithm is simulated on these networks, and the results show that the algorithm has high diagnosis accuracy for various networks.

Edge computing can help the resource-constrained Internet of Things (IoT) devices to perform some complex tasks. Edge computing has many advantages, such as the distributed architecture, low interaction latency, and good resilience. It can provide fast response and reliable service for the IoT applications. There exists an important application in the edge computing environment is to outsource the computationally intensive problems to nearby edge servers, which has become a research hotspot in the area of industry and academia. In this article, we propose a distributed and secure system DSOS for seeking the least squares solution to the overdetermined system of linear equations (OSLE) with the assistance of multiple nearby noncolluding edge servers. Solving this type of linear equations is one of the most common problems for statistics and data mining in IoT. In our system, the coefficient matrix is divided into multiple blocks according to rows. The different blocks are distributed to the different edge servers. All edge servers can help the user to obtain the correct solution to the OSLE by the interactive computation. Our system can ensure the private information about input parameters and final results is not leaked to the participating edge servers. In addition, the mutual verification between the edge servers can ensure the validity of the final results. The experimental evaluations show that the designed system outperforms the existing ones in terms of fast response between the edge server and the user, low computation overload on the edge server side, and high efficiency on the user side.

The fault tolerance of a network can be measured by many parameters. Connectivity is a classic measurement parameter for evaluating the fault tolerance of a network. g-extra connectivity and g-restricted connectivity are generalizations of connectivity, which can better reflect the fault tolerance of a network. Specifically, the g-extra connectivity $\kappa_{g}(G)$ of a graph G is the minimum number of nodes whose removal will disconnect G, and each remaining component has no less than $g+1$ nodes. Furthermore, the g-restricted connectivity $\kappa^{g}(G)$ of G is the minimum number of nodes whose deletion results in a graph being disconnected and the minimum degree of each remaining component is at least g. In general, g-restricted connectivity is not equal to g-extra connectivity of a network. Therefore, many scholars often discuss g-restricted connectivity and g-extra connectivity with regard to different networks separately. In this paper, we show that g-restricted connectivity is equal to g-extra connectivity under some conditions. Then, the relationship we derived can be applied to some known networks such as the data center networks DCell and BCDC, multiprocessor network $(n,k)$-star. In addition, we construct a new network $H(G_{0},G_{1},G_{2};\mathbb{M})$ and prove that our result can be applied to it. In detail, we prove $\kappa^{g}(H(G_{0},G_{1},G_{2};\mathbb{M}))=\kappa_{g}(H(G_{0},G_{1},G_{2};\mathbb{M}))=n+g+1$ for any integers $n\geq 3$ and $ g\displaystyle \leq\lfloor\frac{n-2}{2}\rfloor$.

Abstract Connectivity and diagnosability are two crucial subjects for a network’s ability to tolerate and diagnose faulty processors. The $r$-component connectivity $c\kappa _{r}(G)$ of a network $G$ is the minimum number of vertices whose deletion results in a graph with at least $r$ components. The $r$-component diagnosability $ct_{r}(G)$ of a network $G$ is the maximum number of faulty vertices that the system can guarantee to identify under the condition that there exist at least $r$ fault-free components. This paper first establishes that the $(r+1)$-component connectivity of $k$-ary $n$-cube $Q^{k}_{n}$ is $c\kappa _{r+1}(Q^{k}_{n})=-\frac{1}{2}r^{2}+\Big(2n-\frac{1}{2}\Big)r+1$ for $n\geq 2$, $k\geq 4$ and $1\leq r\leq n$. In view of $c\kappa _{r+1}(Q^{k}_{n})$, we prove that the $(r+1)$-component diagnosabilities of $k$-ary $n$-cube $Q^{k}_{n}$ under the PMC model and MM* model are $ct_{r+1}(Q^{k}_{n})=-\frac{1}{2}r^{2}+\Big(2n-\frac{3}{2}\Big)r+2n$ for $n\geq 4$, $k\geq 4$ and $1\leq r\leq n-1$.

Abstract In the past few years, much importance and attention have been attached to completely independent spanning trees (CISTs). Many results, such as edge-disjoint Hamilton cycles, traceability, number of spanning trees, structural properties, topological indices, etc., have been obtained on line graphs, and researchers have applied the line graphs of some interconnection networks such as generalized hypercubes, augmented cubes, crossed cubes, etc., into data center networks, such as SWCube, AQLCube, BCDC, etc. At the meanwhile, few results of CISTs are reported on the line graphs. In this paper, we establish the relation of edge-disjoint spanning trees in an interconnection network $G$’ with its line graph $G$ by proposing a general algorithm for the first time. By this method, more CISTs can be obtained comparing with results in the literature. Then, the decrease of diameter is discussed and simulation experiments are shown on the line graphs of hypercubes.

Abstract Connectivity is a significant metric to assess the fault tolerance of a network. For a faulty vertex set $H$, the $h$-extra connectivity is defined under the assumption that every component of the network removing $H$ has at least $h+1$ fault-free vertices. Compared to the traditional connectivity, which is defined under the assumption that the network removing $H$ is disconnected or trivial, the $h$-extra connectivity can better reflect the true fault tolerance of the network. The $BCube$ is an important server-centric data center network; it has good fault tolerance and scalability. In this paper, our research focuses on the logical structure of $BCube$, named $BC_{n,k}$, which is actually a specific type of generalized hypercubes. We prove that the 3-extra connectivity of $BC_{n,k}$ is $4(k+1)(n-1)-4n$ for $k\geq 4$ and $n\geq 4$.

Devices in the Internet-of-Things (IoT) are networked and perform massive computations to support various social IoT systems. Applications in social IoT systems often involve complicated computations that are out of the computation capacity of some resource-constrained IoT devices. Thus, how to enable resource-constrained IoT devices to accomplish complex computations efficiently and securely is of significant importance. To address this problem, we develop a secure edge-aided computation scheme for the social IoT systems. We scope the framework of edge-aided computations and identify the security threats in such a system. We define the security requirements that the outsourcing algorithms should meet. Then, we provide two examples of secure outsourcing algorithms (matrix multiplication and modular exponentiation) that meet the given security requirements. The efficiency and security of the proposed algorithms are supported through the theoretical analysis and experimental results.

The public cloud data integrity auditing technique is used to check the integrity of cloud data through the Third Party Auditor (TPA). In order to make it more practical, we propose a new paradigm called integrity auditing based on the keyword with sensitive information privacy for encrypted cloud data. This paradigm is designed for one of the most common scenario, that is, the user concerns the integrity of a portion of encrypted cloud files that contain his/her interested keywords. In our proposed scheme, the TPA who is only provided with the encrypted keyword, can audit the integrity of all encrypted cloud files that contain the user’s interested keyword. Meanwhile, the TPA cannot deduce the sensitive information about which files contain the keyword and how many files contain this keyword. These salient features are realized by leveraging a newly proposed Relation Authentication Label (RAL). The RAL can not only authenticate the relation that files contain the queried keyword, but also be used to generate the auditing proof without sensitive information exposure. We give concrete security analysis showing that the proposed scheme satisfies correctness, auditing soundness and sensitive information privacy. We also conduct the detailed experiments to show the efficiency of our scheme.

As the product of combining Internet of Things (IoT), cloud computing, and traditional healthcare, Intelligent IoT Healthcare (IIoTH) brings us a lot of convenience, meanwhile security and privacy issues have attracted great attention. Dynamic searchable symmetric encryption (DSSE) technique can make the user search the dynamic healthcare information from IIoTH system under the condition that the privacy is protected. In this article, a novel privacy-preserving DSSE scheme for IIoTH system is proposed. It is the first DSSE scheme designed for personal health record (PHR) files database with forward security. We construct the secure index based on hash chain and realize trapdoor updates for resisting file injection attacks. In addition, we realize fine-grained search over encrypted PHR files database of attribute-value type. When the user executes search operations, he/she gets only a matched attribute value instead of the whole file. As a result, the communication cost is reduced and the disclosure of patient's privacy is minimized. The proposed scheme also achieves attribute access control, which allows users have different access authorities to attribute values. The specific security analysis and experiments show the security and the efficiency of the proposed scheme.

Data center networks (DCNs) always strive to ensure high reliability and fault tolerance when Big Data processing and cloud computing are carried out. One effective method is to conduct the fault diagnosis based on subsystem structures (establish the subsystem-based reliability), which can be transformed into solving the problem of the probability that there exists at least one fault-free subnetwork in one network. In this article, we establish the subsystem-based reliability of BCube, which is the first time that fault diagnosis is carried out in the subsystem structures of the DCN. More specifically, we compute the upper and lower bounds on the subsystem-based reliability of BCube and determine the approximation on the subsystem-based reliability of BCube. Furthermore, we conduct some numerical simulations to validate the established analytical formulation. Our results show that the precise value of subsystem-based reliability of BCube can be basically represented by the approximation value of subsystem-based reliability of BCube, which means that it is much easier to evaluate the reliability of the network even when the network scale is sufficient large. Although the analysis is done for a particular network (BCube), the outcome can serve as a useful reference, and can shed light on the effectiveness of the fault diagnosis for other DCNs.

In recent years, Industrial Internet of Things (IIoT) has gradually attracted the attention of the industry owing to its accurate time synchronization, communication accuracy, and high adaptability. As an important data structure, graphs are widely used in IIoT applications, where entities and their relationships can be expressed in the form of graphs. With the widespread adoption of IIoT and cloud computing, an increasing number of individuals or organizations are outsourcing their IIoT graph data to cloud servers to enjoy the unlimited storage space and fast computing service. To protect the privacy of graph data, graphs are usually encrypted before being outsourced. In this article, we propose a search pattern privacy system for approximate shortest distance query of encrypted graphs in IIoT. To realize search pattern privacy, we adopt two noncolluded cloud servers to accomplish different tasks. We leverage the first server to store the encrypted data and perform query operations, and use the second one to rerandomize the contents and shuffle the locations of the queried records. Before queries, we generate the trapdoors by using different random numbers. After queries, we ask the second server to rerandomize the contents of the records that the first server touched. In addition, we shuffle the physical locations of original records by inserting some fake records. In this way, all contents and physical locations of the touched records change, so that the first server cannot distinguish whether two queries are the same or not. To enhance the efficiency on the user side, we further improve this system by moving some heavy workloads from the user to the cloud. The security analysis and the performance evaluation show that our work is secure and efficient.

In the past few years, edge-disjoint spanning trees (EDSTs) have attracted extensive attention due to their applications in reliable communication, fault-tolerant broadcasting, secure message distribution, etc. As one architecture of many interconnection networks, hypercubes (denoted as Qn) play an important role in parallel computing systems, as well as their line graphs (denoted as L(Qn)), but few results of EDSTs in L(Qn) are reported. In this paper, we establish the relation between EDSTs in Qnand EDSTs in L(Qn), then we propose an algorithm to obtain the EDSTs in L(Qn) and present the corresponding simulation experiment to verify its validity.

Independent spanning trees (ISTs) play an important role in secure message distribution, bandwidth as well as fault-tolerant broadcasting. Thus the construction of ISTs on many classes of graphs has been investigated. The n-dimensional folded crossed cube FCQnis a strengthened variation of the n-dimensional crossed cube CQn, which is obtained from CQnby adding edges between any pair of vertices with furthest Hamming distance. In this paper, we study the existence and parallel construction of ISTs on FCQn. We first present the definition of Flag-Mapping and propose an algorithm to obtain the Flag-Mapping of each vertex on n +1 spanning trees of FCQn. Then based on the outputs of above algorithm, we propose a fully parallelized algorithm with the time complexity O(n) by using N processors to construct n +1 ISTs on FCQn, where n ≥ 1 and N =2n, and present the corresponding simulation experiments to verify its validity.

Abstract Connectivity is a classic measure for reliability of a multiprocessor system in the case of processor failures. Extra connectivity and component connectivity are two important indicators of the reliability of a multiprocessor system in presence of failing processors. The $h$-extra connectivity $\kappa _{h}(G)$ of a graph $G$ is the minimum number of nodes whose removal will disconnect $G$, and every remaining component has at least $h+1$ nodes. Moreover, the $h$-component connectivity $c\kappa _{h}(G)$ of $G$ is the minimum number of nodes whose deletion results in a graph with at least $h$ components. However, the extra connectivity and component connectivity of many well-known networks have been independently investigated. In this paper, we determine the relationship between extra connectivity and component connectivity of general networks. As applications, the extra connectivity and component connectivity are explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, Cayley graphs generated by transposition trees and hierarchical hypercubes as well.

Abstract As the number of servers in a data center network (DCN) increases, the probability of server failures is significantly increased. Traditional connectivity is an important metric to measure the reliability of DCN. However, the traditional connectivity of a DCN based on the condition of arbitrary faulty servers is generally lower. Therefore, it is important to increase the connectivity of a DCN by adding some limited conditions for the faulty server set. As a result, $g$-restricted connectivity and $h$-extra connectivity, which are two crucial subjects for a DCN’s ability to tolerate faulty servers, were proposed in the literature. In this paper, we study the $g$-restricted connectivity and $h$-extra connectivity of a new server-centric DCN, called BCDC, based on crossed cube with excellent performance. We prove that the $g$-restricted connectivity of BCDC is 4 for $n=3$ and $2n+g(n-2)-2$ for $n\geq 4$, where $0\leq g\leq n-3$, and the $h$-extra connectivity of BCDC is 4 for $n=3$ and $2n+h(n-2)-2$ for $n\geq 4$, where $0\leq h\leq n-3$.

For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQn is both (2n ‒ 1)-edge-connected and (2n ‒ 1)-nodeconnected (n ≢ 3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQn. So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQn is still open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k − 1 node-ISTs rooted at node 0 in A Q n ( 00...0 ︸ n−k )(n≥k≥4) by proposing an ingenious way of construction and propose a corresponding O(NlogN) time algorithm, where N = 2k is the number of nodes in A Q n ( 00...0 ︸ n−k ) .

We propose two new measures of conditional connectivity to be the extension of R g -connectivity and R g -edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional ( g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) deg G–F ( p) + deg G–F ( q) ≥ 2 g + k for every two distinct vertices p and q in G – F with d( p, q) ≤ d. The ( g, d, k)-conditional(-edge)-connectivity, denoted by κ g,d,k ( λ g,d,k ), is the minimum cardinality of a conditional ( g, d, k)(-edge)-cut. Based on these requirements, we obtain κ 1,1, k , κ 1, d,2 , λ 1,1,1 and λ 1, d,2 for the hypercubes.

The generalized hypercube (GH) is one key interconnection network with excellent topological properties. It contains many other interconnection topologies, such as the hypercube network, the complete graph, the mesh network, and the k-ary n-cube network. It can also be used to construct some data center networks, such as HyperX, BCube, FBFLY, and SWCube. However, the construction cost of GH is high since it contains too many links. In this paper, we propose a novel low cost interconnection architecture called the exchanged generalized hypercube (EGH). We study the properties of EGH, such as the number of edges, the degree of vertices, connectivity, diameter, and diagnosability. Then, we give a routing algorithm to find the shortest path between any two distinct vertices of EGH. Furthermore, we design an algorithm to give disjoint paths between any two distinct vertices of EGH. In addition, we propose two local diagnosis algorithms: LDTEGH and LDWBEGH in EGH under PMC model and MM model, respectively. Simulation results demonstrate that even if the proportion of faulty vertices in EGH is up to 25 percent, the probability that these two diagnosis algorithms can successfully determine the status of vertices is more than 90 percent. As far as the number of edges is concerned, the analysis shows that the construction cost of EGH is much less than that of GH. We could regard this work as the basis for proposing future new high performance topologies.

Influence Maximization (IM) has been extensively applied to many fields, and the viral marketing in today's online social networks (OSNs) is one of the most famous applications, where a group of seed users are selected to activate more users in a distributed cascading fashion. Many prior work explore the IM problem based on the assumption of given budget. However, the budget assumption does not hold in many practical scenarios, since companies might have no sufficient prior knowledge about the market. Moreover, companies prefer a moderately controllable viral marketing that allows them to adjust marketing decision according to the market reaction. In this paper, we propose a new problem, called Controllable social influence maximization (Cosin), to find a set of seed users inside a controllable scope to maximize the benefit given an expected return on investment (ROI). Like the IM problem, the Cosin problem is also NP-hard. We present a distributed multi-hop based framework for the influence estimation, and design a (1/2 + ϵ)-approximate algorithm based on the proposed framework. Moreover, we further present a distributed implementation to accelerate the execution of algorithm for large-scale social networks. Extensive experiments with a billion-scale social network indicate that the proposed algorithms outperform state-of-the-art algorithms in both benefit and running time.

Nowadays people tend to create accounts with multiple social networks (SNs) to enjoy a variety of social network services. User identity linkage (UIL) aims to identify those multiple accounts belonging to a same person. UIL is of great importance to user behavior understanding and prediction, information dissemination, viral marketing, wellness diagnosis, etc. Most of existing solutions typically rely on the embedding of either user's attributes or behaviors into a latent vector space, and establish anchor link based on vector distance. However, these efforts still face challenges originated from the heterogeneity of SNs, incompleteness of user information and lack of enough known anchor links. In this paper, we investigate the UIL problem by presenting a translation-modeling approach-TransLink. It jointly embeds both users and interactive behaviors of various SNs into a unified low-dimensional representation space according to a set of known anchor links. More specifically, we primarily study three typical SNs, e.g, Twitter, Foursquare and Instagram. Before embedding, we abstract schemas of three SNs and extract interaction metapaths for each SN. By doing this we can efficiently address the first two challenges. Furthermore, iterative linkage can ensure linkage performance by using a very small set of known anchor links. Experiment results on two real-world datasets demonstrate the superiority of TransLink over the state-of-the-art approaches.

Fault-tolerance is an important parameter to measure the performance of a network. However, most works only consider the fault of single vertex and ignore the structure-fault of a network. The generalized hypercube G(mr,mr−1,…,m1) is one key interconnection network with excellent topological properties. In this paper, we study the H-structure fault-tolerance of G(mr,mr−1,…,m1) network by studying its H-structure connectivity and H-substructure connectivity for H∈{K1,M,C3,C4,K4}⁠. Since the generalized hypercube network can be used to construct some data center networks, such as BCube, HyperX, and FBFLY, the results in this paper can be applied not only to interconnection networks but also to data center networks.

Summary Currently, Mobile edge computing (MEC) is facing a great challenge that is how to make full use of edge resources to provide a seamless support for compute‐intensive latency‐sensitive applications. Prior studies often make a simple assumption that tasks can be executed upon every edge server, but the assumption does not hold in practical scenarios. Because a specific application task often corresponds to a certain service that provides the corresponding running environment, whereas an edge server only has limited resources and cannot offer too many services. How to decide service deployment of so many types of services among multiple edge servers is also a big challenge. To address the challenge, we study dynamic service deployment for latency‐sensitive applications. We first model the long‐term budget‐constrained latency minimization problem as a multi‐slot latency minimization problem based on the Lyapunov framework. By doing this, the hardness of a problem is significantly reduced, since we never require future information to solve the long‐term optimization. Furthermore, we extend our study by joining the task scheduling optimization, where every edge server is fully utilized in an even more efficient collaborative manner. Our extensive experiments show that the proposed algorithms can bring short latency with low cost.

With the rapid development of cloud computing, many large-scale data centers are being built to provide increasingly popular online application services. This leads to the proposal of data center networks (DCNs) supporting millions of servers with high-network capacity by using only commodity switches. The k-dimensional DCell with n-port switches and tk,n servers, Dk,n⁠, has been proposed as a model for a large-scale DCN with a server-centric structure. In this paper, we study the diagnosability and the g-good-neighbor conditional diagnosability of Dk,n⁠. We prove that: (i) Dk,n is (n+k−1)-diagnosable under the precise diagnosis strategy and (2k+n−2)/(2k+n−2)- diagnosable under the pessimistic diagnosis strategy; (ii) the g-good-neighbor conditional diagnosabilities of Dk,n under the PMC model and the MM* model are both (g+1)k+n−1 (resp. (n+k−g)tg−n+1,n−1) with 0≤g≤n−1 (resp. n≤g≤n+k−2⁠), which is almost (g+1) (resp. tg−n+1,n⁠) times of the traditional diagnosability. These results provide a quantitative evaluation for a large-scale DCN’s reliability and availability.

A scalable storage system becomes more important today for online social networks (OSNs) as the volume of user data increases rapidly. Key-value store uses consistent hashing to save data in a distributed manner. As a defacto standard, it has been widely used in production environments of many OSNs. However, the random nature of hashing always leads to high inter-server traffic. Recently, partitioning and replication are respectively proposed in many existing works where the former aims to minimize the inter-server read traffic and the latter aims to optimize the inter-server write traffic. Nevertheless, the separated manners of optimization cannot efficiently reduce the traffic. Because the inter-server read traffic is changed during replication. In this paper, we suggest that performing partitioning and replication simultaneously could provide probability to further optimize traffic. Then we formulate the problem as a revised graph partitioning with overlaps, since overlaps partitioning naturally corresponds to replication. To solve the problem, we propose a Joint Partitioning and Replication (JPR) scheme. Through extensive experiments with a real world Facebook trace, we evaluate that JPR significantly reduces inter-server traffic with slightly sacrificing storage cost compared to hashing, and preserves a good load balancing across servers as well.

The k-ary n-cube is one of the most attractive interconnection networks for parallel and distributed computing systems. In this paper, we investigate hamiltonian cycle and path embeddings in k-ary n-cubes Qnk based on structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph. Let H be a connected graph with H∈{K1,K1,1,K1,2,K1,3}⁠. We show that for two arbitrary distinct healthy nodes of a faulty Qnk⁠, there exists a fault-free hamiltonian path connecting these two nodes if the number of faulty element is at most a certain number and each faulty element is isomorphic to a connected subgraph of H. We also show that there exists a fault-free hamiltonian cycle if the number of faulty element is at most a certain number and each faulty element is isomorphic to a connected subgraph of H. These results mean that the k-ary n-cube Qnk can tolerate up to 4(n−2) faulty nodes such that Qnk−V(F) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of Qnk⁠.

Summary With the increasing number of users and a huge scale of data, the service providers of Online Social Networks (OSNs) are facing the problem of how to place users' data to multiple servers. Key‐value stores solve the problem based on consistent hashing, and have become a defacto standard. However, random placement manner of hashing cannot preserve social locality, which leads to high intra‐data center traffic and unpredictable response time. Many existing works solve the problem by using graph partitioning algorithms. These works have two drawbacks: First, the social graph is constructed with ordinary pairwise graph that cannot fully reflect multi‐participant interactions often occurring in OSNs. Second, the underlying network topologies of data center have never been considered. This paper investigates the problem of traffic minimization for OSNs data storage. Motivated by maximally preserving both social locality and distance locality, we formulate the problem as two sub‐problems — hypergraph partitioning and partition‐to‐server mapping, and propose a two‐phase data placement (TDP) scheme. Specifically we present two algorithms to solve partition‐to‐server mapping over two widely used network topologies (i.e.,tree and BCube). Evaluations with a large scale Facebook trace show that TDP significantly reduces intra‐data center traffic as well as load balancing across servers. Copyright © 2016 John Wiley & Sons, Ltd.

Target traversing has been an important research topic in wireless sensor networks. Most works in this area consider the coverage issues of the target's moving paths. The support path is to find a path among sensors so that the target's support from the sensors is minimized, where support of the target from a sensor is defined as the inversely proportional to the distance of the target from the sensor. Most existing algorithms ensure the target to stay as close as possible from sensors or deploy sensors to enhance the coverage to the target. In this paper, we take into account the situation where the target must trave the sensor networks within time constraint. We propose some algorithms for the target to not only stay as close as possible from sensors, but also traverse the sensing field within time constraint. Simulations show that the proposed algorithms can solve the traversal path in wireless sensor networks.

Summary Personal cloud storage provides users with convenient data access services. Service providers build distributed storage systems by utilizing cloud resources with distributed hash table (DHT), so as to enhance system scalability. Efficient resource provisioning could not only guarantee service performance, but help providers to save cost. However, the interactions among servers in a DHT‐based cloud storage system depend on the routing process, which makes its execution logic more complicated than traditional multi‐tier applications. In addition, production data centers often comprise heterogeneous machines with different capacities. Few studies have fully considered the heterogeneity of cloud resources, which brings new challenges to resource provisioning. To address these challenges, this paper presents a novel resource provisioning model for service providers. The model utilizes queuing network for analysis of both service performance and cost estimation. Then, the problem is defined as a cost optimization with performance constraints. We propose a cost‐efficient algorithm to decompose the original problem into a sub‐optimization one. Furthermore, we implement a prototype system on top of an infrastructure platform built with OpenStack. It has been deployed in our campus network. Based on real‐world traces collected from our system and Dropbox, we validate the efficiency of our proposed algorithms by extensive experiments. Copyright © 2016 John Wiley & Sons, Ltd.

Reliable broadcasting for a network can be obtained by using completely independent spanning trees(CISTs). Locally twisted cubes are popular networks which have been studied widely in the literature. In this paper, we study the problem of using CISTs to establish reliable broadcasting in locally twisted cubes. We first propose an algorithm, named LTQCIST, to construct two CISTs in locally twisted cubes, then exemplify the construction procedures to construct CISTs. Finally, we prove the correctness of Algorithm LTQCIST and simulate CISTs with JUNG.

The complete binary tree is an important network structure for parallel and distributed computing, which has many nice properties and is often used to be embedded into other interconnection architectures. The locally twisted cube LTQn is an important variant of the hypercube Qn. It has many better properties than Qn with the same number of edges and vertices. In this paper, we prove that the complete binary tree CBTn can be embedded with dilation 2 and congestion 1 into LTQn. Furthermore, it is proven that if there exists an arbitrary faulty node in LTQn, then both the dilation and congestion values will become 2 after reconfiguring CBTn, while if there are two arbitrary faulty nodes in LTQn, then both the dilation and congestion values will become 3 after reconfiguration.

DCell has been proposed for data centers as a server-centric interconnection network structure. DCell can support millions of servers with high network capacity by only using commodity switches. With one exception, we prove that a |$k$| level DCell built with |$n$| port switches is Hamiltonian-connected for |$k \geq 0$| and |$n \geq 2$|⁠. Our proof extends to all Generalized DCell connection rules for |$n\ge 3$|⁠. Then, we propose an |$O(t_k)$| algorithm for finding a Hamiltonian path in |$DCell_{k}$|⁠, where |$t_k$| is the number of servers in |$DCell_{k}$|⁠. Furthermore, we prove that |$DCell_{k}$| is |$(n +k - 4)$|-fault Hamiltonian-connected and |$(n +k - 3)$|-fault Hamiltonian. In addition, we show that a partial DCell is Hamiltonian-connected if it conforms to a few practical restrictions.

In recent years, there are many new findings on independent spanning trees (ISTs for short) in hypercubes, crossed cubes, locally twisted cubes, and Mobius cubes, which all belong to a more general network category called bijective connection networks (BC networks). However, little progress has been made for ISTs in general BC networks. In this paper, we first propose the definitions of conditional BC networks and V -dimensional-permutation. We then give a linear parallel algorithm of ISTs rooted at an arbitrary vertex in conditional BC networks, which include hypercubes, crossed cubes, locally twisted cubes, and Mobius cubes, based on the ascending circular dimensional-permutation, where the ISTs are all isomorphic to the binomial-like tree. In addition, we show that there exists an efficient algorithm to construct a spanning tree rooted at an arbitrary vertex in any BC network Xn, and all V-dimensional-permutations can be used to construct spanning trees isomorphic to the n-level binomial tree and rooted at an arbitrary vertex in Xn.

Obtaining spectrum information efficiently is key to cognitive radio networks (CRNs). The database-driven approach has emerged recently as an alternative or supplement for spectrum sensing, and has been quickly adopted by the government and the industry. Within database-driven CRNs, master devices obtain spectrum information by direct connection to a spectrum database, while slave devices can only access spectrum information indirectly via masters. Out-of-band connections with a second network interface which do not depend on the primary spectrum channels can be used for the communication of spectrum information among masters and slaves. Alternatively, the in-band approach completely based on primary spectrum channels can be used, which eliminates the need for out-of-band connections and eases the adoption of the database-driven spectrum sharing. In this paper, we study the in-band bootstrapping process for database-driven multi-hop CRNs, where master/slave devices form a multi-hop networks and slaves need multi-hop communications to obtain spectrum information from the master during bootstrapping. We propose several protocols to reduce the bootstrapping time and protocol overhead. According to the analysis and simulation results, our proposed protocols can greatly improve the performance.

Independent spanning trees (ISTs) on networks have applications in networks such as reliable communication protocols, the multi-node broadcasting, one-to-all broadcasting, reliable broadcasting and secure message distribution. However, there is a problem on ISTs on graphs: If a graph G is n-connected (n ≥ 1), then there are n ISTs rooted at an arbitrary vertex on G. This problem has remained open for n ≥ 5. In this paper, we consider the construction of ISTs on Möbius cubes—a class of hypercube variants. An O(N log N) recursive algorithm is proposed to construct n ISTs rooted at an arbitrary vertex on the n-dimensional Möbius cube Mn, where N = 2n is the number of vertices in Mn. Furthermore, we prove that each IST obtained by our algorithm is isomorphic to an n-level binomial-like tree with the height n + 1 for n ≥ 2.

In traditional identity-based encryption schemes, security will be entirely lost once secret keys are exposed. However, with more and more use of mobile and unprotected devices, key exposure seems unavoidable. To deal with this problem, we newly propose a forward-secure identity-based public-key encryption scheme. In this primitive, the exposure of the secret key in one period doesn't affect the security of the ciphertext generated in previous periods. Any parameter in our scheme has at most log-squared complexity in terms of the total number of time periods. We also give the semantic security notions of forward-secure identity-based public-key encryption. The proposed scheme is proven semantically secure in the standard model. As far as we are concerned, it is the first forward-secure identity-based public-key encryption scheme without random oracles.

In wireless ad hoc networks, the constructed topology is preferred to be planar since a planar topology enables guaranteed delivery of packets without a routing table. Previous planar structures are statically constructed for the whole network. However, environmental or network dynamics such as channel status, interference, or residual energy will prevent such structures from providing the best service to the network. In this paper, we present a t-adjustable planar structure (TAP) which enables each node to adjust the topology independently via a parameter t and allows nodes to have different path loss exponent. TAP is based on three well-known planar structures: Gabriel Graph, Relative Neighborhood Graph, and Local Minimum Spanning Tree. We show properties of TAP by proof or simulation: (1) It preserves connectivity; (2) it is planar, sparse, and symmetric; (3) it preserves all minimum energy path when t = 1 for all nodes; and (4) the average transmission power, interference, and node degree decrease as t increases and the maximum node degree is bounded by 6 when t = 3 for all nodes.

In wireless ad hoc networks, a planar topology enables nodes to deliver packets without a routing table. Pervious planar structures are fixed for the whole network. However, environmental or network dynamics such as channel status, interference or energy will prevent such structures from providing the best service to the network. In this paper, we present a t-adjustable planar structure (TAP) which enables nodes to adjust the topology independently and allows nodes to have different path loss exponent. We show by proof or simulation properties of TAP: (1) It preserves connectivity; (2) It is planar, sparse and symmetric; (3) It preserves all minimum energy path when t=1 for all nodes; (4) The average transmission power, interference and node degree decrease as t increases and the maximum node degree is bounded by 6 when t=3 for all nodes.

The dimensions of twisted cubes in the original definition of twisted cubes are only limited to odd integers. In this paper, we first extend the dimensions of twisted cubes to all the positive integers. Then, we introduce the concept of the set of restricted faulty nodes into twisted cubes. We further prove that under the condition that each node of the n-dimensional twisted cube TQnhas at least one fault-free neighbor its restricted connectivity is 2n - 2, which is almost as twice as that of TQnunder the condition of arbitrary faulty nodes, the same as that of the n-dimensional hypercube. Moreover, we give an O(N log N) fault-free unicast algorithm, where N denotes the node number of TQn-1. Finally, we give the simulation result of the expected length of the fault-free path gotten by our algorithm.

Twisted cubes are variants of hypercubes. In this paper, we study the optimal embeddings of paths of all possible lengths between two arbitrary distinct nodes in twisted cubes. We use TQnto denote the n-dimensional twisted cube and use dist(TQn, u, v) to denote the distance between two nodes u and v in TQn, where n ges l is an odd integer. The original contributions of this paper are as follows: 1) We prove that a path of length l can be embedded between u and v with dilation 1 for any two distinct nodes u and v and any integer l with dist(TQn, u, v) + 2 les l les 2n- 1 (n ges 3) and 2) we find that there exist two nodes u and v such that no path of length dist(TQn, u, v) + l can be embedded between u and v with dilation 1 (n ges 3). The special cases for the nonexistence and existence of embeddings of paths between nodes u and v and with length dist(TQn, u, v) + 1 are also discussed. The embeddings discussed in this paper are optimal in the sense that they have dilation 1

Crossed cubes are attractive alternatives to the popular hypercubes with many advantageous properties. In this paper, we study embeddings of paths of different lengths between any two distinct nodes in crossed cubes.We prove two important results: (a) Paths of all possible lengths greater than or equal to the distance between any two nodes plus 2 can be embedded between the two nodes with dilation 1; And (b) in the n-dimensional crossed cube, for any two integers n \ge 3 and l with 1 \le l \le \left\lceil {\frac{{n + 1}}{2}} \right\rceil -1, there always exist two nodes x and y, such that the distance between x and y is l and any path of length l + 1 cannot be embedded between x and y with dilation 1. The results improve those provided by Fan, Lin, and Jia.

Processor fault diagnosis takes an important role in fault-tolerant computing on multiprocessor systems. There are two classical diagnosis strategies - the precise strategy and the pessimistic strategy, both of which are based on the well-known PMC diagnostic model. Nevertheless, the degree of diagnosability of the system is limited under these two strategies. A better method, called the t/k-diagnosis strategy, is proposed by Somani and Peleg, in which the identified fault-set is allowed to contain at most k fault-free processors. Using this diagnosis strategy, the degree of diagnosability of the hypercube increases greatly as the number of the fault-free processors in the fault-set increases. We study the t/k-diagnosability of so-called BC graphs that include hypercubes, crossed cubes, Mobius cubes, and twisted cubes, etc. We show that any n-dimensional BC graph is t(n, k)/k-diagnosable when n/spl ges/4 and 0/spl les/k/spl les/n, where t(n,k)=(k+1)n-1/2(k+1)(k+2)+1. Therefore, the crossed cube, the Mobius cube, and the twisted cube all have the same t/k-diagnosability as the hypercube. As a result, the algorithms developed for diagnosis on the hypercube may also be used to diagnose multiprocessor systems whose network topologies are based on BC graphs.

The crossed cube is an important variant of the hypercube. The n-dimensional crossed cube has only about half diameter, wide diameter, and fault diameter of those of the n-dimensional hypercube. Embeddings of trees, cycles, shortest paths, and Hamiltonian paths in crossed cubes have been studied in literature. Little work has been done on the embedding of paths except shortest paths, and Hamiltonian paths in crossed cubes. In this paper, we study optimal embedding of paths of different lengths between any two nodes in crossed cubes. We prove that paths of all lengths between [(n+1)/2] and 2/sup n/-1 can be embedded between any two distinct nodes with a dilation of 1 in the n-dimensional crossed cube. The embedding of paths is optimal in the sense that the dilation of the embedding is 1. We also prove that [(n+1)/2]+1 is the shortest possible length that can be embedded between arbitrary two distinct nodes with dilation 1 in the n-dimensional crossed cube.

Diagnosability of a multiprocessor system is an important study topic in the parallel processing area. As a hypercube variant, the crossed cube has many attractive properties. The diameter, wide diameter and fault diameter of it are all approximately half those of the hypercube. The power with which the crossed cube simulates trees and cycles is stronger than the hypercube. Because of these advantages, the crossed cube has attracted much attention from researchers. In this paper, we show that the n-dimensional crossed cube is n-diagnosable under a major diagnosis model-the comparison diagnosis model proposed by Malek and Maeng (1981) if n /spl ges/ 4. According to this, the polynomial algorithm presented by Sengupta and Dahbura (1992) may be used to diagnose the n-dimensional crossed cube, provided that the number of the faulty nodes in the n-dimensional crossed cube does not exceed n. The conclusion also indicates that the diagnosability of the n-dimensional crossed cube is the same as that of the n-dimensional hypercube when n /spl ges/ 5 and better than that of the n-dimensional hypercube when n = 4.

Diagnosability of a multiprocessor system is one important study topic in the parallel processing area. As a hypercube variant, the crossed cube has many attractive properties. The diameter, wide diameter and fault diameter of it are all approximately half of those of the hypercube. The power that the crossed cube simulates trees and cycles is stronger than the hypercube. Because of these advantages of the crossed cube, it has attracted much attention from researchers. We show that the n-dimensional crossed cube is n-diagnosable under a major diagnosis model-the comparison diagnosis model proposed by Malek (1980) and Maeng and Malek (1981) if n/spl ges/4. According to this, the polynomial algorithm presented by Sengupta and Dahbura (1992) may be used to diagnose the n-dimensional crossed cube, provided that the number of the faulty nodes in the n-dimensional crossed cube does not exceed n. The conclusion of this paper also indicates that the diagnosability of the n-dimensional crossed cube is the same as that of the n-dimensional hypercube when n>5 and better than that of the n-dimensional hypercube when n=4.

The recently introduced interconnection networks, the Mobius cubes, are hypercube variants that have some better properties than hypercubes. The n-dimensional Mobius cube M/sub n/ is a regular graph with 2/sup n/ nodes and n2/sup n-1/ edges. The diameter of M/sub n/ is about one half that of the n-dimensional hypercube Q/sub n/ and the average number of steps between nodes for M/sub n/ is about two-thirds of the average for Q/sub n/, and 1-M/sub n/ has dynamic performance superior to that of Q/sub n/. Of course, the symmetry of M/sub n/ is not superior to that of Q/sub n/, i.e., Q/sub n/ is both node symmetric and edge symmetric , whereas M/sub n/ is, in general, neither node symmetric (n/spl ges/4) nor edge symmetric (n/spl ges/3). In this paper, we study the diagnosability of M/sub n/. We use two diagnosis strategies, both based on the so-called PMC diagnostic model-the precise (one-step) diagnosis strategy proposed by Preparata et al. (1967) and the pessimistic diagnosis strategy proposed by Friedman (1975). We show that the diagnosability of M/sub n/ is the same as that of Q/sub n/, i.e., M/sub n/ is n-diagnosable under the precise diagnosis strategy and (2n-2)/(2n-2)-diagnosable under the pessimistic diagnosis strategy.