12941596
Adaptive Fault-Tolerant Routing in Cube-Based Multicomputers Using Safety Vectors
Reliable communication in cube-based multicomputers using the safety vector concept is studied in this paper. In our approach, each node in a cube-based multicomputer of dimension n is associated with a safety vector of n bits, which is an approximated measure of the number and distribution of faults in the neighborhood. The safety vector of each node can be easily calculated through n-1 rounds of information exchange among neighboring nodes. Optimal unicasting between two nodes is guaranteed if the kth bit of the safety vector of the source node is one, where k is the Hamming distance between the source and destination nodes. The concept of dynamic adaptivity is introduced, representing the ability of a routing algorithm to dynamically adjust its routing adaptivity based on fault distribution in the neighborhood. The feasibility of the proposed unicasting can be easily determined at the source node by comparing its safety vector with the Hamming distance between the source and destination nodes. The proposed unicasting can also be used in disconnected hypercubes, where nodes in a hypercube are disjointed (into two or more parts). We then extend the safety vector concept to general cube-based multicomputers.
2254959
Local-Safety-Information-Based Broadcasting in Hypercube Multicomputers with Node and Link Faults
This paper presents a method to cope with fault-tolerant broadcasting in hypercube multicomputers with both node and link faults. The local safety concept is extended to faulty hypercubes with both node and link faults. The local-safety-based algorithm is used in a fully unsafe hypercube, where there is no safe node. A fully unsafe hypercube can be split into a set of maximal safe subcubes. We show that if these maximal safe subcubes meet certain requirements given in the paper, broadcasting can still be carried out successfully and in some case optimal broadcast is still possible. The method is extended to fault-tolerant routing and multicasting when the system contains both node and link faults.
7582647
On self-similarity and hamiltonicity of dual-cubes
The dual-cube is a newly proposed topology for interconnection networks, which uses low dimensional hypercubes as building blocks. The primary advantages of the dual-cube over the hypercube are that, with the same node degree n, the dual-cube contains 2/sup n-1/ times more nodes than the hypercube and, with the same amount of nodes, the dual-cube has approximately 50% less links than the hypercube. This paper was focused on the investigations of the structural self-similarity and the Hamiltonian property of the dual-cube. It was shown that a dual-cube can be recursively constructed from lower dimensional dual-cubes and, conversely, a dual-cube can be recursively decomposed into lower dimensional dual-cubes. It was also proved that all dual-cubes are Hamiltonian. There exist multiple Hamiltonian cycles on a dual-cube, among which, [(n-1)/2] cycles are edge-disjoint. It was illustrated that rings and linear arrays can be effectively emulated on dual-cubes. Some strategies for track sharing in efficient VLSI layout design were also discussed.
17371165
QoS Routing in Hypercube Multicomputers
In this paper, we present a coding method to capture QoS information in hypercube multicomputers. The coding method is based on a localized algorithm where each node interacts with its neighbors to gather QoS information. Specifically, each node maintains a QoS vector where the k-th element represents the guaranteed QoS performance to a destination that is k hops away. The localized algorithm exhibits desirable properties of self-stabilizing, self-optimizing, and self-healing. Simulation results show that this coding method provides a good approximation of the minimum QoS value to a k-hop destination and, at the same time, uses a relatively small number of packets to propagate a change in link state (QoS value) compared with the classical distributed Bellman-Ford method.
16257632
XYZ: a scalable, partially centralized lookup service for large-scale peer-to-peer systems
Peer-to-peer (P2P) systems are characterized by direct access between peer computers, rather than through a centralized server. File sharing is the dominant P2P application on the Internet, allowing users to easily contribute, search and obtain content. P2P systems can be categorized by the degrees of centralization. For fully centralized systems, the lookup service will not be available when the central directory server is down. For purely decentralized and unstructured systems, since there is no information about which nodes are likely to have the relevant files, searching essentially amounts to random search. This makes the lookup service unscalable and unpredictable. The objective of this paper is to design a partially centralized, scalable and self-organizing lookup service (XYZ) for wide area P2P systems. A clustering method is used to create the system backbone by connecting the cluster heads together and a color clustering method is adopted to create color overlays and minimize the searching space. Simulations and analysis are also provided. Extensions are proposed to achieve better performance
27746153
Broadcasting in Faulty Cube-Connected-Cycles with Minimum Recovery Time
We propose a broadcasting algorithm for a faulty Cube-Connected-Cycles multiprocessor. The broadcasting algorithm delivers a message to all the nodes non-redundantly using a binomial tree. The traffic generated because of the recovery is guaranteed to be minimum.
10351800
Identification of functional links between genes using phylogenetic profiles
MOTIVATION
Genes with identical patterns of occurrence across the phyla tend to function together in the same protein complexes or participate in the same biochemical pathway. However, the requirement that the profiles be identical (i) severely restricts the number of functional links that can be established by such phylogenetic profiling; (ii) limits detection to very strong functional links, failing to capture relations between genes that are not in the same pathway, but nevertheless subserve a common function and (iii) misses relations between analogous genes. Here we present and apply a method for relaxing the restriction, based on the probability that a given arbitrary degree of similarity between two profiles would occur by chance, with no biological pressure. Function is then inferred at any desired level of confidence.


RESULTS
We derive an expression for the probability distribution of a given number of chance co-occurrences of a pair of non-homologous orthologs across a set of genomes. The method is applied to 2905 clusters of orthologous genes (COGs) from 44 fully sequenced microbial genomes representing all three domains of life. Among the results are the following. (1) Of the 51 000 annotated intrapathway gene pairs, 8935 are linked at a level of significance of 0.01. This is over 30-fold greater than the 271 intrapathway pairs obtained at the same confidence level when identical profiles are used. (2) Of the 540 000 interpathway genes pairs, some 65 000 are linked at the 0.01 level of significance, some 12 standard deviations beyond the number expected by chance at this confidence level. We speculate that many of these links involve nearest-neighbor path, and discuss some examples. (3) The difference in the percentage of linked interpathway and intrapathway genes is highly significant, consistent with the intuitive expectation that genes in the same pathway are generally under greater selective pressure than those that are not. (4) The method appears to recover well metabolic networks. This is illustrated by the TCA cycle which is recovered as a highly connected, weighted edge network of 30 of its 31 COGs. (5) The fraction of pairs having a common pathway is a symmetric function of the Hamming distance between their profiles. This finding, that the functional correlation between profiles with near maximum Hamming distance is as large as between profiles with near zero Hamming distance, and as statistically significant, is plausibly explained if the former group represents analogous genes.
11280225
Realistic modeling of bird flight animations
In this paper we describe a physics-based method for synthesis of bird flight animations. Our method computes a realistic set of wingbeats that enables a bird to follow the specified trajectory. We model the bird as an articulated skeleton with elastically deformable feathers. The bird motion is created by applying joint torques and aerodynamic forces over time in a forward dynamics simulation. We solve for each wingbeat motion separately by optimizing for wingbeat parameters that create the most natural motion. The final animation is constructed by concatenating a series of optimal wingbeats. This detailed bird flight model enables us to produce flight motions of different birds performing a variety of maneuvers including taking off, cruising, rapidly descending, turning, and landing.
1297042
An Access Control Scheme for Partially Ordered Set Hierarchy with Provable Security
In a hierarchical structure, an entity has access to another if and only if the former is a superior of the later. The access control scheme for a hierarchy represented by a partially ordered set (poset) has been researched intensively in the past years. In this paper, we propose a new scheme that achieves the best performance of previous schemes and is provably secure under a comprehensive security model.
1990124
Removable edges in a cycle of a 4-connected graph
Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting in the graph G − e; second, for all the vertices x of degree 3 in G − e, delete x from G − e and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by Ge .I fGe is still 4-connected, then e is called a removable edgeof G. In this paper, we investigate the problem on how many removable edges there are in a cycle of a 4-connected graph, and give examples to show that our results are in some sense the best possible. © 2004 Elsevier B.V. All rights reserved. MSC: 05C40; 05C38; 05C75
2622485
Diagnostic test generation for sequential circuits
Efficient diagnosis of faults in VLSI circuits requires high quality diagnostic test sets. In this work novel techniques for diagnostic test generation are proposed that require significantly less time than previous methods. The set of fault pairs left undistinguished by a detection-oriented test set is first filtered to target only testable faults. Then diagnostic test generation is performed using a genetic algorithm (GA) combined with a diagnostic fault simulator. A new fitness metric is proposed for the GA that accurately measures the quality of candidate sequences while requiring a limited amount of CPU time. Experimental results illustrate the effectiveness of the approach for sequential circuits.