Practical Scalable Consensus for Pseudo-Synchronous Distributed Systems: Formal Proof
Thomas Hérault, Aurélien Bouteiller, George Bosilca, Marc Gamell, Keita Teranishi, Manish Parashar, Jack J. Dongarra · 2015
The ability to consistently handle faults in a distributed en-vironment 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 re-sources. 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 logarith-mic 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 effi-ciency and scalability through a set of benchmarks and two fault tolerant scientific applications. CCS Concepts •Computing methodologies → Distributed algorithms; •Computer systems organization→Reliability; Fault-tolerant network topologies; •Software and its engi-neering → Software fault tolerance;