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 language | English (US) |
|---|---|
| Pages (from-to) | 13-22 |
| Number of pages | 10 |
| Journal | ACM SIGPLAN Notices |
| Volume | 48 |
| Issue number | 8 |
| DOIs | |
| State | Published - Aug 1 2013 |
Fingerprint
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 journal › Article
}
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 -