Scalable and fault tolerant failure detection and consensus

Amogh Katti; Giuseppe Di Fatta; Thomas Naughton; Christian Engelmann

doi:10.1145/2802658.2802660

Scalable and fault tolerant failure detection and consensus

Amogh Katti, Giuseppe Di Fatta, Thomas Naughton, Christian Engelmann

Intelligent Systems and Facilities

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Scopus citations

Abstract

Future extreme-scale high-performance computing systems will be required to work under frequent component failures. The MPI Forum's User Level Failure Mitigation proposal has introduced an operation, MPI Comm shrink, to synchronize the alive processes on the list of failed processes, so that applications can continue to execute even in the presence of failures by adopting algorithm-based fault tolerance techniques. This MPI Comm shrink operation requires a fault tolerant failure detection and consensus algorithm. This paper presents and compares two novel failure detection and consensus algorithms. The proposed algorithms are based on Gossip protocols and are inherently fault- Tolerant and scalable. The proposed algorithms were implemented and tested using the Extreme-scale Simulator. The results show that in both algorithms the number of Gossip cycles to achieve global consensus scales logarithmically with system size. The second algorithm also shows better scalability in terms of memory and network bandwidth usage and a perfect synchronization in achieving global consensus.

Original language	English
Title of host publication	Proceedings of the 22nd European MPI Users' Group Meeting, EuroMPI 2015
Publisher	Association for Computing Machinery
ISBN (Electronic)	9781450337953
DOIs	https://doi.org/10.1145/2802658.2802660
State	Published - Sep 21 2015
Event	22nd European MPI Users' Group Meeting, EuroMPI 2015 - Bordeaux, France Duration: Sep 21 2015 → Sep 23 2015

Publication series

Name	ACM International Conference Proceeding Series
Volume	21-23-September-2015

Conference

Conference	22nd European MPI Users' Group Meeting, EuroMPI 2015
Country/Territory	France
City	Bordeaux
Period	09/21/15 → 09/23/15

Funding

This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research. The author Amogh Katti is supported by the Felix Scholarship for his PhD project

Keywords

Consensus
Failure detection
Fault- Tolerant MPI
Gossip protocols
User-level failure mitigation

Access to Document

10.1145/2802658.2802660

Cite this

@inproceedings{ebd93967d5c049a0a473f88786f0ad06,

title = "Scalable and fault tolerant failure detection and consensus",

abstract = "Future extreme-scale high-performance computing systems will be required to work under frequent component failures. The MPI Forum's User Level Failure Mitigation proposal has introduced an operation, MPI Comm shrink, to synchronize the alive processes on the list of failed processes, so that applications can continue to execute even in the presence of failures by adopting algorithm-based fault tolerance techniques. This MPI Comm shrink operation requires a fault tolerant failure detection and consensus algorithm. This paper presents and compares two novel failure detection and consensus algorithms. The proposed algorithms are based on Gossip protocols and are inherently fault- Tolerant and scalable. The proposed algorithms were implemented and tested using the Extreme-scale Simulator. The results show that in both algorithms the number of Gossip cycles to achieve global consensus scales logarithmically with system size. The second algorithm also shows better scalability in terms of memory and network bandwidth usage and a perfect synchronization in achieving global consensus.",

keywords = "Consensus, Failure detection, Fault- Tolerant MPI, Gossip protocols, User-level failure mitigation",

author = "Amogh Katti and {Di Fatta}, Giuseppe and Thomas Naughton and Christian Engelmann",

note = "Publisher Copyright: {\textcopyright} 2015 ACM.; 22nd European MPI Users' Group Meeting, EuroMPI 2015 ; Conference date: 21-09-2015 Through 23-09-2015",

year = "2015",

month = sep,

day = "21",

doi = "10.1145/2802658.2802660",

language = "English",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery",

booktitle = "Proceedings of the 22nd European MPI Users' Group Meeting, EuroMPI 2015",

}

Katti, A, Di Fatta, G, Naughton, T & Engelmann, C 2015, Scalable and fault tolerant failure detection and consensus. in Proceedings of the 22nd European MPI Users' Group Meeting, EuroMPI 2015., a13, ACM International Conference Proceeding Series, vol. 21-23-September-2015, Association for Computing Machinery, 22nd European MPI Users' Group Meeting, EuroMPI 2015, Bordeaux, France, 09/21/15. https://doi.org/10.1145/2802658.2802660

Scalable and fault tolerant failure detection and consensus. / Katti, Amogh; Di Fatta, Giuseppe; Naughton, Thomas et al.
Proceedings of the 22nd European MPI Users' Group Meeting, EuroMPI 2015. Association for Computing Machinery, 2015. a13 (ACM International Conference Proceeding Series; Vol. 21-23-September-2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Scalable and fault tolerant failure detection and consensus

AU - Katti, Amogh

AU - Di Fatta, Giuseppe

AU - Naughton, Thomas

AU - Engelmann, Christian

PY - 2015/9/21

Y1 - 2015/9/21

N2 - Future extreme-scale high-performance computing systems will be required to work under frequent component failures. The MPI Forum's User Level Failure Mitigation proposal has introduced an operation, MPI Comm shrink, to synchronize the alive processes on the list of failed processes, so that applications can continue to execute even in the presence of failures by adopting algorithm-based fault tolerance techniques. This MPI Comm shrink operation requires a fault tolerant failure detection and consensus algorithm. This paper presents and compares two novel failure detection and consensus algorithms. The proposed algorithms are based on Gossip protocols and are inherently fault- Tolerant and scalable. The proposed algorithms were implemented and tested using the Extreme-scale Simulator. The results show that in both algorithms the number of Gossip cycles to achieve global consensus scales logarithmically with system size. The second algorithm also shows better scalability in terms of memory and network bandwidth usage and a perfect synchronization in achieving global consensus.

AB - Future extreme-scale high-performance computing systems will be required to work under frequent component failures. The MPI Forum's User Level Failure Mitigation proposal has introduced an operation, MPI Comm shrink, to synchronize the alive processes on the list of failed processes, so that applications can continue to execute even in the presence of failures by adopting algorithm-based fault tolerance techniques. This MPI Comm shrink operation requires a fault tolerant failure detection and consensus algorithm. This paper presents and compares two novel failure detection and consensus algorithms. The proposed algorithms are based on Gossip protocols and are inherently fault- Tolerant and scalable. The proposed algorithms were implemented and tested using the Extreme-scale Simulator. The results show that in both algorithms the number of Gossip cycles to achieve global consensus scales logarithmically with system size. The second algorithm also shows better scalability in terms of memory and network bandwidth usage and a perfect synchronization in achieving global consensus.

KW - Consensus

KW - Failure detection

KW - Fault- Tolerant MPI

KW - Gossip protocols

KW - User-level failure mitigation

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

U2 - 10.1145/2802658.2802660

DO - 10.1145/2802658.2802660

M3 - Conference contribution

AN - SCOPUS:84983398159

T3 - ACM International Conference Proceeding Series

BT - Proceedings of the 22nd European MPI Users' Group Meeting, EuroMPI 2015

PB - Association for Computing Machinery

T2 - 22nd European MPI Users' Group Meeting, EuroMPI 2015

Y2 - 21 September 2015 through 23 September 2015

ER -

Scalable and fault tolerant failure detection and consensus

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this