### Abstract

The impossibility of distributed consensus with one faulty process is a result with important consequences for real world distributed systems e.g., commits in replicated databases. Since proofs are not immune to faults and even plausible proofs with a profound formalism can conclude wrong results, we validate the fundamental result named FLP after Fischer, Lynch and Paterson. We present a formalization of distributed systems and the aforementioned consensus problem. Our proof is based on Hagen Völzer's paper "A constructive proof for FLP". In addition to the enhanced confidence in the validity of Völzer's proof, we contribute the missing gaps to show the correctness in Isabelle/HOL. We clarify the proof details and even prove fairness of the infinite execution that contradicts consensus. Our Isabelle formalization can also be reused for further proofs of properties of distributed systems.

### License

BSD License

### Topics

- Computer science/Concurrency

### Session FLP

- Multiset
- AsynchronousSystem
- ListUtilities
- Execution
- FLPSystem
- FLPTheorem
- FLPExistingSystem

## Cite

×

FLP-AFP

    @article{FLP-AFP,
      author  = {Benjamin Bisping and Paul-David Brodmann and Tim Jungnickel and Christina Rickmann and Henning Seidler and Anke Stüber and Arno Wilhelm-Weidner and Kirstin Peters and Uwe Nestmann},
      title   = {A Constructive Proof for FLP},
      journal = {Archive of Formal Proofs},
      month   = {May},
      year    = {2016},
      note    = {\url{https://isa-afp.org/entries/FLP.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Apr 18, 2020 : Isabelle2020
- Jun 11, 2019 : Isabelle2019
- Aug 16, 2018 : Isabelle2018
- Oct 10, 2017 : Isabelle2017
- Dec 17, 2016 : Isabelle2016-1
- May 18, 2016 : Isabelle2016