521738
A distributed formation of orthogonal convex polygons in mesh-connected multicomputer
The rectangular faulty block model is the most commonly used fault model in designing a fault-tolerant and deadlock-free routing algorithm in mesh-connected multicomputers. The convexity of a rectangle facilitates simple and efficient ways to route messages around fault regions using relatively few virtual channels to avoid deadlock. However, such a faulty block may include many nonfaulty nodes which are disabled, i.e. they are not involved in the routing process. Therefore, it is important to define a fault region that is convex, and at the same time, to include a minimum number of nonfaulty nodes. In this paper we propose a simple and efficient distributed algorithm that can quickly construct a set of special convex polygons, called orthogonal convex polygons, from a given set of rectangular faulty blocks in a 2-D mesh (or 2-D torus). The formation of orthogonal convex polygons is done through a labeling scheme based on iterative message exchanges among neighboring nodes.
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.
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.
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.
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.
15943479
Efficient face candidates selector for face detection
Abstract In this paper an efficient face candidates selector is proposed for face detection tasks in still gray level images. The proposed method acts as a selective attentional mechanism. Eye-analogue segments at a given scale are discovered by finding regions which are roughly as large as real eyes and are darker than their neighborhoods. Then a pair of eye-analogue segments are hypothesized to be eyes in a face and combined into a face candidate if their placement is consistent with the anthropological characteristic of human eyes. The proposed method is robust in that it can deal with illumination changes and moderate rotations. A subset of the FERET data set and the BioID face database are used to evaluate the proposed method. The proposed face candidates selector is successful in 98.75% and 98.6% cases, respectively.
17480069
Similarity-based Web service matchmaking
With the increasing growth in popularity of Web services, matchmaking of relevant Web services becomes a significant challenge. Commonly, Web service is described by WSDL and published on UDDI registers. UDDI provides limited search facilities allowing only a keyword-based search of businesses, services, and the so called tModels based on names and identifiers. This category-based keyword-browsing method is clearly insufficient. Semantic Web service uses DAML-S instead of WSDL to represent capabilities of Web services. This improvement enables software agents or search engines to automatically find appropriate Web services via ontologies and reasoning algorithm enriched methods. However, the high cost of formally defining to the heavy and complicated services makes this improvement widespread adoption unlikely. To cope with these limitations, we have developed a suite of methods which assesses the similarity of Web services to achieve matchmaking. In particular, we present a conceptual model which classifies properties of Web services into four categories. For each category, a similarity assessment method has been given. In Web service matchmaking process, these similarity assessment methods can be used together or individually. Experiments highlight complementary contributions that our work makes to facilitate Web service matchmaking.
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.
32836256
Minimum average distance of strong orientations of graphs
The average distance of a graph (strong digraph) G, denoted by µ(G) is the average, among the distances between all pairs (ordered pairs) of vertices of G. If G is a 2-edge-connected graph, then µ→min(G) is the minimum average distance taken over all strong orientations of G. A lower bound for µ→min(G) in terms of the order, size, girth and average distance of G is established and shown to be sharp for several complete multipartite graphs. It is shown that there is no upper bound for µ→min(G) in terms of µ(G). However, if every edge of G lies on 3-cycle, then it is shown that µ→min(G) ≤ 7/4 µ(G). This bound is improved for maximal planar graphs to 5/3 µ(G) and even further to 3/2 µ(G) for eulerian maximal planar graphs and for outerplanar graphs with the property that every edge lies on 3-cycle. In the last case the bound is shown to be sharp.
17000130
Removable Edges in Longest Cycles of 4-Connected Graphs
Abstract.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 the graph G−e; second, for all 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 G⊖e. If G⊖e is 4-connected, then e is called a removable edge of G. In this paper we obtain some results on removable edges in a longest cycle of a 4-connected graph G. We also show that for a 4-connected graph G of minimum degree at least 5 or girth at least 4, any edge of G is removable or contractible.