A Graph Partitioning Approach to Sequential Diagnosis.

Abstract

This paper describes a generalized sequential diagnosis algorithm whose analysis leads to strong diagnosability results for a variety of multiprocessor interconnection topologies. The overall complexity of this algorithm in terms of total testing and syndrome decoding time is linear in the number of edges in the interconnection graph and the total number of iterations of diagnosis and repair needed by the algorithm is bounded by the diameter of the interconnection graph. The degree of diagnosability of this algorithm for a given interconnection graph is shown to be directly related to a graph parameter which we refer to as the partition number. We approximate this graph parameter for several interconnection topologies and thereby obtain lower bounds on degree of diagnosability achieved by our algorithm on these topologies.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 11, 1996
Accession Number
ADA310754

Entities

People

  • Sanjeev Khanna
  • W. K. Fuchs

Organizations

  • Purdue University

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Communication Channels
  • Decoding
  • Diameters
  • Electronics
  • Embedding
  • Equations
  • Fault Tolerance
  • Grids
  • Inequalities
  • Intervals
  • Iterations
  • Notation
  • Observers
  • Topology
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Fault Tolerant Diagnosis of Black and White Balloon Isolation Tests Using ¥.
  • Parallel and Distributed Computing.
  • Statistical inference.