Practical scalable consensus for pseudo-synchronous distributed systems

Thomas Herault; Aurelien Bouteiller; George Bosilca; Marc Gamell; Keita Teranishi; Manish Parashar; Jack Dongarra

doi:10.1145/2807591.2807665

Practical scalable consensus for pseudo-synchronous distributed systems

Thomas Herault, Aurelien Bouteiller, George Bosilca, Marc Gamell, Keita Teranishi, Manish Parashar, Jack Dongarra

Computer Science and Mathematics Div

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

13 Scopus citations

Abstract

The ability to consistently handle faults in a distributed environment requires, among a small set of basic routines, an agreement algorithm allowing surviving entities to reach a consensual decision between a bounded set of volatile resources. This paper presents an algorithm that implements an Early Returning Agreement (ERA) in pseudo-synchronous systems, which optimistically allows a process to resume its activity while guaranteeing strong progress. We prove the correctness of our ERA algorithm, and expose its logarithmic behavior, which is an extremely desirable property for any algorithm which targets future exascale platforms. We detail a practical implementation of this consensus algorithm in the context of an MPI library, and evaluate both its efficiency and scalability through a set of benchmarks and two fault tolerant scientific applications.

Original language	English
Title of host publication	Proceedings of SC 2015
Subtitle of host publication	The International Conference for High Performance Computing, Networking, Storage and Analysis
Publisher	IEEE Computer Society
ISBN (Electronic)	9781450337236
DOIs	https://doi.org/10.1145/2807591.2807665
State	Published - Nov 15 2015
Event	International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2015 - Austin, United States Duration: Nov 15 2015 → Nov 20 2015

Publication series

Name	International Conference for High Performance Computing, Networking, Storage and Analysis, SC
Volume	15-20-November-2015
ISSN (Print)	2167-4329
ISSN (Electronic)	2167-4337

Conference

Conference	International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2015
Country/Territory	United States
City	Austin
Period	11/15/15 → 11/20/15

Funding

The authors would like to thank Robert Clay, Michael Heroux and Josep Gamell for interesting discussions related to this work. This work is partially supported by the NSF (award #1339820), and the CREST project of the Japan Science and Technology Agency (JST). This work is also partially supported by the U.S. Department of Energy (DOE) National Nuclear Security Administration (NNSA) Advanced Simulation and Computing (ASC) program. Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy's National Nuclear Security Administration under contract DE-AC04-94AL85000.

Funders	Funder number
Sandia Corporation
U.S. Department of Energy's National Nuclear Security Administration	DE-AC04-94AL85000
National Science Foundation	1339820
U.S. Department of Energy
National Sleep Foundation
Lockheed Martin Corporation
National Nuclear Security Administration	ASC
Sandia National Laboratories
Japan Science and Technology Agency
Core Research for Evolutional Science and Technology

Keywords

MPI
agreement
fault-tolerance

Access to Document

10.1145/2807591.2807665

Cite this

Herault, T., Bouteiller, A., Bosilca, G., Gamell, M., Teranishi, K., Parashar, M., & Dongarra, J. (2015). Practical scalable consensus for pseudo-synchronous distributed systems. In Proceedings of SC 2015: The International Conference for High Performance Computing, Networking, Storage and Analysis Article a31 (International Conference for High Performance Computing, Networking, Storage and Analysis, SC; Vol. 15-20-November-2015). IEEE Computer Society. https://doi.org/10.1145/2807591.2807665

Herault, Thomas ; Bouteiller, Aurelien ; Bosilca, George et al. / Practical scalable consensus for pseudo-synchronous distributed systems. Proceedings of SC 2015: The International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, 2015. (International Conference for High Performance Computing, Networking, Storage and Analysis, SC).

@inproceedings{4f6e372fa1aa4a90be78c1295babb496,

title = "Practical scalable consensus for pseudo-synchronous distributed systems",

abstract = "The ability to consistently handle faults in a distributed environment requires, among a small set of basic routines, an agreement algorithm allowing surviving entities to reach a consensual decision between a bounded set of volatile resources. This paper presents an algorithm that implements an Early Returning Agreement (ERA) in pseudo-synchronous systems, which optimistically allows a process to resume its activity while guaranteeing strong progress. We prove the correctness of our ERA algorithm, and expose its logarithmic behavior, which is an extremely desirable property for any algorithm which targets future exascale platforms. We detail a practical implementation of this consensus algorithm in the context of an MPI library, and evaluate both its efficiency and scalability through a set of benchmarks and two fault tolerant scientific applications.",

keywords = "MPI, agreement, fault-tolerance",

author = "Thomas Herault and Aurelien Bouteiller and George Bosilca and Marc Gamell and Keita Teranishi and Manish Parashar and Jack Dongarra",

note = "Publisher Copyright: {\textcopyright} 2015 ACM.; International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2015 ; Conference date: 15-11-2015 Through 20-11-2015",

year = "2015",

month = nov,

day = "15",

doi = "10.1145/2807591.2807665",

language = "English",

series = "International Conference for High Performance Computing, Networking, Storage and Analysis, SC",

publisher = "IEEE Computer Society",

booktitle = "Proceedings of SC 2015",

}

Herault, T, Bouteiller, A, Bosilca, G, Gamell, M, Teranishi, K, Parashar, M & Dongarra, J 2015, Practical scalable consensus for pseudo-synchronous distributed systems. in Proceedings of SC 2015: The International Conference for High Performance Computing, Networking, Storage and Analysis., a31, International Conference for High Performance Computing, Networking, Storage and Analysis, SC, vol. 15-20-November-2015, IEEE Computer Society, International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2015, Austin, United States, 11/15/15. https://doi.org/10.1145/2807591.2807665

Practical scalable consensus for pseudo-synchronous distributed systems. / Herault, Thomas; Bouteiller, Aurelien; Bosilca, George et al.
Proceedings of SC 2015: The International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, 2015. a31 (International Conference for High Performance Computing, Networking, Storage and Analysis, SC; Vol. 15-20-November-2015).

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

TY - GEN

T1 - Practical scalable consensus for pseudo-synchronous distributed systems

AU - Herault, Thomas

AU - Bouteiller, Aurelien

AU - Bosilca, George

AU - Gamell, Marc

AU - Teranishi, Keita

AU - Parashar, Manish

AU - Dongarra, Jack

PY - 2015/11/15

Y1 - 2015/11/15

N2 - The ability to consistently handle faults in a distributed environment requires, among a small set of basic routines, an agreement algorithm allowing surviving entities to reach a consensual decision between a bounded set of volatile resources. This paper presents an algorithm that implements an Early Returning Agreement (ERA) in pseudo-synchronous systems, which optimistically allows a process to resume its activity while guaranteeing strong progress. We prove the correctness of our ERA algorithm, and expose its logarithmic behavior, which is an extremely desirable property for any algorithm which targets future exascale platforms. We detail a practical implementation of this consensus algorithm in the context of an MPI library, and evaluate both its efficiency and scalability through a set of benchmarks and two fault tolerant scientific applications.

AB - The ability to consistently handle faults in a distributed environment requires, among a small set of basic routines, an agreement algorithm allowing surviving entities to reach a consensual decision between a bounded set of volatile resources. This paper presents an algorithm that implements an Early Returning Agreement (ERA) in pseudo-synchronous systems, which optimistically allows a process to resume its activity while guaranteeing strong progress. We prove the correctness of our ERA algorithm, and expose its logarithmic behavior, which is an extremely desirable property for any algorithm which targets future exascale platforms. We detail a practical implementation of this consensus algorithm in the context of an MPI library, and evaluate both its efficiency and scalability through a set of benchmarks and two fault tolerant scientific applications.

KW - MPI

KW - agreement

KW - fault-tolerance

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

U2 - 10.1145/2807591.2807665

DO - 10.1145/2807591.2807665

M3 - Conference contribution

AN - SCOPUS:84966671012

T3 - International Conference for High Performance Computing, Networking, Storage and Analysis, SC

BT - Proceedings of SC 2015

PB - IEEE Computer Society

T2 - International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2015

Y2 - 15 November 2015 through 20 November 2015

ER -

Herault T, Bouteiller A, Bosilca G, Gamell M, Teranishi K, Parashar M et al. Practical scalable consensus for pseudo-synchronous distributed systems. In Proceedings of SC 2015: The International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society. 2015. a31. (International Conference for High Performance Computing, Networking, Storage and Analysis, SC). doi: 10.1145/2807591.2807665

Practical scalable consensus for pseudo-synchronous distributed systems

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this