Improved precise fault diagnosis algorithm for hypercube-like graphs

Tai Ling Ye, Dun Wei Cheng, Sun Yuan Hsieh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The system reliability is an important issue for multiprocessor systems. The fault diagnosis has become crucial for achieving high reliability in multiprocessor systems. In the comparisonbased model, it allows a processor to perform diagnosis by contrasting the responses from a pair of neighboring processors through sending the identical assignment. Recently, Ye and Hsieh devised an precise fault diagnosis algorithm to detect all faulty processors for hypercube-like networks by using the MM* model with O(N(log2 N)2) time complexity, where N is the cardinality of processor set in multiprocessor systems. On the basis of Hamiltonian cycle properties, we improve the aforementioned results by presenting an O(N)-time precise fault diagnosis algorithm to detect all faulty processors for hypercube-like networks by using the MM* model.

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings
EditorsMinming Li, Lusheng Wang, T-H. Hubert Chan
PublisherSpringer Verlag
Pages107-112
Number of pages6
ISBN (Print)9783319487489
DOIs
Publication statusPublished - 2016 Jan 1
Event10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016 - Hong Kong, China
Duration: 2016 Dec 162016 Dec 18

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10043 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016
CountryChina
CityHong Kong
Period16-12-1616-12-18

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improved precise fault diagnosis algorithm for hypercube-like graphs'. Together they form a unique fingerprint.

Cite this