Adoption protocols for fanout-optimal fault-tolerant termination detection

Jonathan Lifflander, Phil Miller, Laxmikant Kale

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 single-process 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)
Title of host publicationPPoPP 2013 - Proceedings of the 2013 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
Pages13-22
Number of pages10
DOIs
StatePublished - 2013
Event18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2013 - Shenzhen, China
Duration: Feb 23 2013Feb 27 2013

Publication series

NameProceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP

Other

Other18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2013
CountryChina
CityShenzhen
Period2/23/132/27/13

Keywords

  • high performance computing
  • termination detection

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Adoption protocols for fanout-optimal fault-tolerant termination detection'. Together they form a unique fingerprint.

Cite this