Verification of Clock Synchronization Algorithms: Experiments on a combination of deductive tools - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2005

Verification of Clock Synchronization Algorithms: Experiments on a combination of deductive tools

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 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~\cite{lamport_cs} and the Fault-tolerant Midpoint algorithm of Lundelius-Lynch, satisfy Schneider's general conditions for correctness. The proofs are completely formalized in Isabelle/HOL. We identify the 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 arithmetic like ICS and CVC Lite.
Fichier principal
Vignette du fichier
barsotti_prensa_tiu.pdf (236.8 Ko) Télécharger le fichier
Loading...

Dates and versions

inria-00000638 , version 1 (10-11-2005)

Identifiers

  • HAL Id : inria-00000638 , version 1

Cite

Damian Barsotti, Leonor Prensa Nieto, Alwen Tiu. Verification of Clock Synchronization Algorithms: Experiments on a combination of deductive tools. Fifth International Workshop on Automated Verification of Critical Systems 2005 - AVoCS '05, Ranko Lazic, Rajagopal Nagarajan, Nikolaos Papanikolaou, Sep 2005, Coventry/UK. ⟨inria-00000638⟩
108 View
199 Download

Share

Gmail Facebook X LinkedIn More