The Doomsday Distributed Termination Detection Protocol

Michael James Livesey, Ronald Morrison, D.S. Munro

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

Distributed termination detection (DTD) algorithms are important since they detect globally stable states in distributed computations. Here we introduce a new DTD mechanism, the Doomsday protocol together with its proof of correctness. Doomsday is generic since it forms the basis for a number of new and existing DTD algorithms for which the correctness proof may be reused. The paper describes the Doomsday protocol, provides its formal proof, derives one new DTD algorithm and shows how other hitherto unrelated algorithms, Dijkstra-Scholten, Task Balancing and Credit Recovery, can be derived from the protocol. The paper concludes by examining various properties of the protocol in the context of existing DTD algorithms.

Original languageEnglish
Pages (from-to)419-431
Number of pages13
JournalDistributed Computing
Volume19
Issue number5-6
DOIs
Publication statusPublished - Apr 2007

Keywords

  • protocols
  • correctness
  • distributed termination detection
  • DETECTION ALGORITHMS

Fingerprint

Dive into the research topics of 'The Doomsday Distributed Termination Detection Protocol'. Together they form a unique fingerprint.

Cite this