An (N-1)-resilient algorithm for distributed termination detection

Author

Lai, Ten-Hwang ; Wu, Li-Fen

Author_Institution

Dept. of Comput. & Inf. Sci., Ohio State Univ., Columbus, OH, USA

Volume

6

Issue

1

fYear

1995

fDate

1/1/1995 12:00:00 AM

Firstpage

63

Lastpage

78

Abstract

The paper presents a fault tolerant termination detection algorithm based on a previous fault sensitive scheme by Dijkstra and Scholten. The proposed algorithm can tolerate any number of crash failures. It runs as efficiently as its nonfault tolerant predecessor if no process actually fails during the computation, and otherwise incurs only a small amount of cost for each actual failure. It is assumed that the underlying communication network provides such services as reliable end to end communication, failure detection, and fail flush

Keywords

computational complexity; distributed algorithms; fault tolerant computing; reliability; crash failures; distributed algorithm; distributed termination detection; fail flush; failure detection; fault sensitive scheme; fault tolerant termination detection algorithm; message complexity; resilient algorithm; underlying communication network; Communication networks; Costs; Detectors; Face detection; Fault detection; Fault tolerance; Fault tolerant systems; Information science; Protocols; Telecommunication network reliability;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.363410

Filename

363410