Formal Verification of Consensus Algorithms Tolerating Malicious Faults

Bernadette Charron-Bost 1 Henri Debrat 2 Stephan Merz 2, *
* Corresponding author
2 VERIDIS - VERIfication pour les systèmes DIStribués
Inria Nancy - Grand Est, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications : UMR7503
Abstract : Consensus is the paradigmatic problem in fault-tolerant distributed computing: it requires network nodes that communicate by message passing to agree on a common value even in the presence of (benign or malicious) faults. Several algorithms for solving Consensus exist, but few of them have been rigorously verified, much less so formally. The Heard-Of model proposes a simple, unifying framework for defining distributed algorithms in the presence of communication faults. Algorithms proceed in communication-closed rounds, and assumptions on the faults tolerated by the algorithm are stated abstractly in the form of communication predicates. Extending previous work on the case of benign faults, our approach relies on the fact that properties such as Consensus can be verified over a coarse-grained, round-based representation of executions. We have encoded the Heard-Of model in the interactive proof assistant Isabelle/HOL and have used this encoding to formally verify three Consensus algorithms based on synchronous and asynchronous assumptions. Our proofs give some new insights into the correctness of the algorithms, in particular with respect to transient faults.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00639048
Contributor : Stephan Merz <>
Submitted on : Tuesday, November 8, 2011 - 9:40:53 AM
Last modification on : Wednesday, April 3, 2019 - 1:23:12 AM
Long-term archiving on : Sunday, December 4, 2016 - 11:20:58 AM

File

main.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Bernadette Charron-Bost, Henri Debrat, Stephan Merz. Formal Verification of Consensus Algorithms Tolerating Malicious Faults. 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2011), Oct 2011, Grenoble, France. pp.120-134, ⟨10.1007/978-3-642-24550-3_11⟩. ⟨hal-00639048⟩

Share

Metrics

Record views

628

Files downloads

455