Verification of clock synchronization algorithms: Experiments on a combination of deductive tools

Damián Barsotti, Leonor Prensa Nieto*, Alwen Tiu

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    12 Citations (Scopus)

    Abstract

    We report on an experiment in combining the theorem prover Isabelle with automatic first-order arithmetic provers to increase automation on the verification of distributed protocols. As a case study for the experiment we verify several averaging clock synchronization algorithms. We present a formalization of Schneider's generalized clock synchronization protocol [Sch87] in Isabelle/HOL. Then, we verify that the convergence functions used in two clock synchronization algorithms, namely, the Interactive Convergence Algorithm (ICA) of Lamport and Melliar-Smith [LMS85] and the Fault-tolerant Midpoint algorithm of Lundelius-Lynch [LL84], satisfy Schneider's general conditions for correctness. The proofs are completely formalized in Isabelle/HOL. We identify parts of the proofs which are not fully automatically proven by Isabelle built-in tactics and show that these proofs can be handled by automatic first-order provers with support for arithmetics.

    Original languageEnglish
    Pages (from-to)321-341
    Number of pages21
    JournalFormal Aspects of Computing
    Volume19
    Issue number3
    DOIs
    Publication statusPublished - Aug 2007

    Fingerprint

    Dive into the research topics of 'Verification of clock synchronization algorithms: Experiments on a combination of deductive tools'. Together they form a unique fingerprint.

    Cite this