View in EDS

A Nearly Optimal Comparison-Based Diagnosis Algorithm for Systems of Arbitrary Topology.

Saved in:
Bibliographic Details
Title: A Nearly Optimal Comparison-Based Diagnosis Algorithm for Systems of Arbitrary Topology.
Authors: Ziwich, Roverli P.1, Duarte, Elias P.1
Source: IEEE Transactions on Parallel & Distributed Systems. Nov2016, Vol. 27 Issue 11, p3131-3143. 13p.
Subjects: Computer diagnostic software, Parallel processing, Distributed computing, Fault-tolerant computing, Computer reliability, Computer systems, Multiprocessors
Abstract: Comparison-based diagnosis is a practical approach to detect faults in hardware, software, and parallel and distributed systems. Diagnosis is based on the comparison of task outputs returned by pairs of system units. This work introduces a novel diagnosis algorithm to identify faults in $t$ -diagnosable systems of arbitrary topology under the MM* model. The complexity of the proposed algorithm is $O(t^2 \Delta N)$ in the worst case for a system with $N$ units, where $t$ denotes the maximum number of faulty units allowed and $\Delta$ corresponds to the maximum degree of a unit in the system. This complexity is nearly optimal in the sense that it is very close to that of traversing the syndrome once. Besides the algorithm specification and correctness proofs, simulations results are also presented, showing the typical performance of the algorithm for different systems. [ABSTRACT FROM PUBLISHER]
Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 118689405
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A Nearly Optimal Comparison-Based Diagnosis Algorithm for Systems of Arbitrary Topology.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Ziwich%2C+Roverli+P%2E%22">Ziwich, Roverli P.</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Duarte%2C+Elias+P%2E%22">Duarte, Elias P.</searchLink><relatesTo>1</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Parallel+%26+Distributed+Systems%22">IEEE Transactions on Parallel & Distributed Systems</searchLink>. Nov2016, Vol. 27 Issue 11, p3131-3143. 13p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computer+diagnostic+software%22">Computer diagnostic software</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+processing%22">Parallel processing</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+computing%22">Distributed computing</searchLink><br /><searchLink fieldCode="DE" term="%22Fault-tolerant+computing%22">Fault-tolerant computing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+reliability%22">Computer reliability</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink><br /><searchLink fieldCode="DE" term="%22Multiprocessors%22">Multiprocessors</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Comparison-based diagnosis is a practical approach to detect faults in hardware, software, and parallel and distributed systems. Diagnosis is based on the comparison of task outputs returned by pairs of system units. This work introduces a novel diagnosis algorithm to identify faults in $t$ <alternatives><inline-graphic xlink:type="simple" xlink:href="duartejr-ieq1-2524004.gif"/></alternatives> -diagnosable systems of arbitrary topology under the MM* model. The complexity of the proposed algorithm is $O(t^2 \Delta N)$<alternatives> <inline-graphic xlink:type="simple" xlink:href="duartejr-ieq2-2524004.gif"/></alternatives> in the worst case for a system with $N$<alternatives> <inline-graphic xlink:type="simple" xlink:href="duartejr-ieq3-2524004.gif"/></alternatives> units, where $t$<alternatives> <inline-graphic xlink:type="simple" xlink:href="duartejr-ieq4-2524004.gif"/></alternatives> denotes the maximum number of faulty units allowed and $\Delta$<alternatives> <inline-graphic xlink:type="simple" xlink:href="duartejr-ieq5-2524004.gif"/></alternatives> corresponds to the maximum degree of a unit in the system. This complexity is nearly optimal in the sense that it is very close to that of traversing the syndrome once. Besides the algorithm specification and correctness proofs, simulations results are also presented, showing the typical performance of the algorithm for different systems. [ABSTRACT FROM PUBLISHER]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=118689405
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1109/TPDS.2016.2524004
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 13
        StartPage: 3131
    Subjects:
      – SubjectFull: Computer diagnostic software
        Type: general
      – SubjectFull: Parallel processing
        Type: general
      – SubjectFull: Distributed computing
        Type: general
      – SubjectFull: Fault-tolerant computing
        Type: general
      – SubjectFull: Computer reliability
        Type: general
      – SubjectFull: Computer systems
        Type: general
      – SubjectFull: Multiprocessors
        Type: general
    Titles:
      – TitleFull: A Nearly Optimal Comparison-Based Diagnosis Algorithm for Systems of Arbitrary Topology.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Ziwich, Roverli P.
      – PersonEntity:
          Name:
            NameFull: Duarte, Elias P.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 11
              Text: Nov2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 10459219
          Numbering:
            – Type: volume
              Value: 27
            – Type: issue
              Value: 11
          Titles:
            – TitleFull: IEEE Transactions on Parallel & Distributed Systems
              Type: main
ResultId 1