A general method for maximizing the error-detecting ability of distributed algorithms

Author

Schollmeyer, Martina ; McMillin, Bruce

Author_Institution

Res. Inst. for Appl. Software Technol., Munich, Germany

Volume

8

Issue

2

fYear

1997

fDate

2/1/1997 12:00:00 AM

Firstpage

164

Lastpage

172

Abstract

The bound on component failures and their spatial distribution govern the fault tolerance of any candidate error-detecting algorithm. For distributed memory multiprocessors, the specific algorithm and the topology of the processor interconnection network define these bounds. This paper introduces the maximal fault index, derived from the system topology and local communication patterns, to demonstrate how a maximal number of simultaneous component failures can be tolerated for a particular interconnection network and error-detecting algorithm. The index is used to design a mapping of processes to processor groups such that the error-detecting ability of the algorithm is preserved for certain multiple simultaneous processor failures

Keywords

distributed algorithms; error detection codes; fault tolerant computing; multiprocessor interconnection networks; component failures; distributed algorithms; distributed memory multiprocessors; error-detecting ability; fault tolerance; interconnection network; local communication patterns; maximal fault index; multiple simultaneous processor failures; processor interconnection network; simultaneous component failures; spatial distribution; system topology; Algorithm design and analysis; Delay; Distributed algorithms; Fault detection; Fault tolerance; Fault tolerant systems; Multiprocessor interconnection networks; Network topology; Safety; Simultaneous localization and mapping;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.577258

Filename

577258