Adoption protocols for fanout-optimal fault-tolerant termination detection

Jonathan Lifflander, Phil Miller, Laxmikant V. Kale

Research output: Contribution to journalArticlepeer-review


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
Issue number8
StatePublished - Aug 2013


  • Fault Tolerance
  • Termination Detection

ASJC Scopus subject areas

  • Computer Science(all)


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

Cite this