Adoption protocols for fanout-optimal fault-tolerant termination detection

Jonathan Lifflander, Phil Miller, Laxmikant V Kale

Research output: Contribution to journalArticle

Abstract

Termination detection is relevant for signaling completion (all processors are idle and no messages are in flight) of many operations in distributed systems, including work stealing algorithms, dynamic data exchange, and dynamically structured computations. In the face of growing supercomputers with increasing likelihood that each job may encounter faults, it is important for high-performance computing applications that rely on termination detection that such an algorithm be able to tolerate the inevitable faults. We provide a trio of new practical fault tolerance schemes for a standard approach to termination detection that are easy to implement, present low overhead in both theory and practice, and have scalable costs when recovering from faults. These schemes tolerate all singleprocess faults, and are probabilistically tolerant of faults affecting multiple processes.We combine the theoretical failure probabilities we can calculate for each algorithm with historical fault records from real machines to show that these algorithms have excellent overall survivability.

Original languageEnglish (US)
Pages (from-to)13-22
Number of pages10
JournalACM SIGPLAN Notices
Volume48
Issue number8
DOIs
StatePublished - Aug 1 2013

Fingerprint

Supercomputers
Electronic data interchange
Fault tolerance
Costs

Keywords

  • Fault Tolerance
  • Termination Detection

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Adoption protocols for fanout-optimal fault-tolerant termination detection. / Lifflander, Jonathan; Miller, Phil; Kale, Laxmikant V.

In: ACM SIGPLAN Notices, Vol. 48, No. 8, 01.08.2013, p. 13-22.

Research output: Contribution to journalArticle

Lifflander, Jonathan ; Miller, Phil ; Kale, Laxmikant V. / Adoption protocols for fanout-optimal fault-tolerant termination detection. In: ACM SIGPLAN Notices. 2013 ; Vol. 48, No. 8. pp. 13-22.
@article{9da0d4f0696241c5a96977be28d13eed,
title = "Adoption protocols for fanout-optimal fault-tolerant termination detection",
abstract = "Termination detection is relevant for signaling completion (all processors are idle and no messages are in flight) of many operations in distributed systems, including work stealing algorithms, dynamic data exchange, and dynamically structured computations. In the face of growing supercomputers with increasing likelihood that each job may encounter faults, it is important for high-performance computing applications that rely on termination detection that such an algorithm be able to tolerate the inevitable faults. We provide a trio of new practical fault tolerance schemes for a standard approach to termination detection that are easy to implement, present low overhead in both theory and practice, and have scalable costs when recovering from faults. These schemes tolerate all singleprocess faults, and are probabilistically tolerant of faults affecting multiple processes.We combine the theoretical failure probabilities we can calculate for each algorithm with historical fault records from real machines to show that these algorithms have excellent overall survivability.",
keywords = "Fault Tolerance, Termination Detection",
author = "Jonathan Lifflander and Phil Miller and Kale, {Laxmikant V}",
year = "2013",
month = "8",
day = "1",
doi = "10.1145/2517327.2442519",
language = "English (US)",
volume = "48",
pages = "13--22",
journal = "ACM SIGPLAN Notices",
issn = "1523-2867",
publisher = "Association for Computing Machinery (ACM)",
number = "8",

}

TY - JOUR

T1 - Adoption protocols for fanout-optimal fault-tolerant termination detection

AU - Lifflander, Jonathan

AU - Miller, Phil

AU - Kale, Laxmikant V

PY - 2013/8/1

Y1 - 2013/8/1

N2 - Termination detection is relevant for signaling completion (all processors are idle and no messages are in flight) of many operations in distributed systems, including work stealing algorithms, dynamic data exchange, and dynamically structured computations. In the face of growing supercomputers with increasing likelihood that each job may encounter faults, it is important for high-performance computing applications that rely on termination detection that such an algorithm be able to tolerate the inevitable faults. We provide a trio of new practical fault tolerance schemes for a standard approach to termination detection that are easy to implement, present low overhead in both theory and practice, and have scalable costs when recovering from faults. These schemes tolerate all singleprocess faults, and are probabilistically tolerant of faults affecting multiple processes.We combine the theoretical failure probabilities we can calculate for each algorithm with historical fault records from real machines to show that these algorithms have excellent overall survivability.

AB - Termination detection is relevant for signaling completion (all processors are idle and no messages are in flight) of many operations in distributed systems, including work stealing algorithms, dynamic data exchange, and dynamically structured computations. In the face of growing supercomputers with increasing likelihood that each job may encounter faults, it is important for high-performance computing applications that rely on termination detection that such an algorithm be able to tolerate the inevitable faults. We provide a trio of new practical fault tolerance schemes for a standard approach to termination detection that are easy to implement, present low overhead in both theory and practice, and have scalable costs when recovering from faults. These schemes tolerate all singleprocess faults, and are probabilistically tolerant of faults affecting multiple processes.We combine the theoretical failure probabilities we can calculate for each algorithm with historical fault records from real machines to show that these algorithms have excellent overall survivability.

KW - Fault Tolerance

KW - Termination Detection

UR - http://www.scopus.com/inward/record.url?scp=84885230297&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84885230297&partnerID=8YFLogxK

U2 - 10.1145/2517327.2442519

DO - 10.1145/2517327.2442519

M3 - Article

AN - SCOPUS:84885230297

VL - 48

SP - 13

EP - 22

JO - ACM SIGPLAN Notices

JF - ACM SIGPLAN Notices

SN - 1523-2867

IS - 8

ER -