Synthesis of Algorithm-Based Fault-Tolerant Systems from Dependence Graphs

B. Vinnakonta, Niraj K. Jha

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


Algorithm-Based Fault Tolerance (ABFT) is a scheme to improve the reliability of parallel architectures used for computation-intensive tasks. The exact implementation of an ABFT scheme is algorithm-dependent. ABFT systems have very low overhead compared to other fault tolerance schemes with similar benefits. Few results are available in the area of general synthesis of ABFT systems. A two-stage approach to the synthesis of ABFT systems is proposed. In the first stage a system-level code is chosen to encode the data used in the algorithm. In the second stage the optimal architecture to implement the scheme is chosen using dependence graphs. Dependence graphs are a graph-theoretic form of algorithm representation. We demonstrate that not all architectures are ideal for the implementation of a particular ABFT scheme. We propose new measures to characterize the fault tolerance capability of a system to better exploit the proposed synthesis method. Dependence graphs can also be used for the synthesis of ABFT schemes for non-linear problems. An example of a fault-tolerant median filter is provided to illustrate their utility for such problems.

Original languageEnglish (US)
Pages (from-to)864-874
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number8
StatePublished - Aug 1993

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


  • Algorithm-based fault tolerance
  • checksum end
  • coding
  • concurrent error detection
  • dependence graphs
  • fault detectability
  • fault locatability
  • system synthesis for fault tolerance


Dive into the research topics of 'Synthesis of Algorithm-Based Fault-Tolerant Systems from Dependence Graphs'. Together they form a unique fingerprint.

Cite this