A fast pessimistic diagnosis algorithm for generalized hypercube multicomputer systems

Duh, Dyi-Rong; Chen, Chien-Hong; Chang, Keh-Ning
September 2012
Journal of Supercomputing;
The reliability of processors is an important issue for designing a massively parallel processing system for which fault-tolerant computing is crucial. In order to achieve high system reliability and availability, a faulty processor (node) when found should be replaced by a fault-free processor. Within a multiprocessor system, the technique of identifying faulty nodes by constructing tests on the nodes and interpreting the test outcomes is known as system-level diagnosis. The topological structure of a multicomputer system can be modeled by a graph of which the vertices and edges correspond to nodes and links of the system, respectively. This work presents a system-level diagnosis algorithm for a generalized hypercube which is an attractive variance of a hypercube. The proposed algorithm is based on the PMC model and can isolate all faulty nodes to within a set which contains at most one fault-free node. If the total number of nodes to be diagnosed in a generalized hypercube is N, the proposed algorithm can run in O( Nlog N) time, and being superior to Yang's algorithm proposed in 2004, it can diagnose not only a hypercube but also a generalized hypercube.


Related Articles

  • Fault-Tolerant Cycle Embedding in Restricted Hypercube-like Networks with More Faulty Nodes. Qiang Dong; Xiao-Fan Yang // Journal of Information Science & Engineering;Mar2012, Vol. 28 Issue 2, p419 

    The hypercube-like networks are a class of important generalization of the popular hypercube interconnection networks for parallel computing. This paper is concerned with the fault-tolerant cycle embedding ability of a subclass of hypercube-like networks, called restricted hypercube-like...

  • The Fault-tolerant Routing in Enhanced Hypercube.  // Journal of Systems Science & Information;Mar2011, Vol. 9 Issue 1, p1 

    No abstract available.

  • Probability-based Fault-tolerant Routing in Hypercubes. Al-Sadi, J.; Day, K.; Ould-Khaoua, M. // Computer Journal;Sep2001, Vol. 44 Issue 5, p368 

    This paper describes a new fault-tolerant routing algorithm for the hypercube, using the concept of probability vectors. To compute these vectors, a node first determines its faulty set, which represents the set of all its neighbouring nodes that are faulty or unreachable due to faulty nodes or...

  • The Edge-Fault-Tolerant Bipancyclicity of the Even k-ary n-cube. Fang, Jywe-Fei // Computer Journal;Feb2011, Vol. 54 Issue 2, p255 

    The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks, including the ring, torus and hypercube, that are attractive in both theoretical interests and practical systems can be regarded as...

  • Cycles Embedding in Faulty Enhanced Hypercube. Yihan Fan; Hongmei Liu; Yanjuan Zhang; Qing Liu // Journal of Systems Science & Information;Jun2012, Vol. 10 Issue 2, p151 

    The enhanced hypercube Qn,k (n, k are positive integers, 1 ≤ k ≤ n - 1) is one of the most versatile and efficient interconnection networks (networks for short) so far discovered for parallel computation. In this paper, the properties related to cycles embedding in...

  • Gaussian Networks For Scalable Distributed Systems. Hsu, W.-J.; Chung, M. J.; Hu, Z. // Computer Journal;1996, Vol. 39 Issue 5, p417 

    The interconnection topology of a network plays a key role in determining the performance and cost of routing messages in the system. Presently, there are many known results about individual network topologies and their applications. However, relatively few results exist about the relations...

  • Analysis of Fault Tolerance in Hypercube. Radhika, P.; G., Sri Sowmya; Reddy, P. Venkat; Rao, D. Srinivasa // International Journal of Advanced Research in Computer Science;Apr2014 Special Issue, Vol. 5 Issue 4, p101 

    Multiprocessor systems which afford a high degree of parallelism are used in variety of applications. The extremely stringent reliability requirement has made the provision of fault-tolerance an important aspect in the design of such systems. This paper presents a new technique called wormhole...

  • Topology and Routing Algorithm Based on the Combination Gray Code with Johnson Code. Xiaoqiang Yang; Huimin Du; Jungang Han // Journal of Computers;Mar2009, Vol. 4 Issue 3, p259 

    Hypercubes utilizing Gray Code are used widely as the interconnection networks of parallel computer systems. But an n-dimensional hypercube has 2n nodes, when the size of a network have been increases added nodes must be 2i times more than its nodes and increase the degree of nodes , which...

  • An adaptive task-level fault-tolerant approach to Grid. Wu, Yongwei; Yuan, Yulai; Yang, Guangwen; Zheng, Weimin // Journal of Supercomputing;Feb2010, Vol. 51 Issue 2, p97 

    A strong failure recovery mechanism handling diverse failures in heterogeneous and dynamic Grid is so important to ensure the complete execution of long-running applications. Although there have been various efforts made to address this issue, existing solutions either focus on employing only...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics