Automated Formal Verification of the TTEthernet Synchronization Quality


Steiner, W., Dutertre, B. (2011). Automated Formal Verification of the TTEthernet Synchronization Quality. In: Bobaru, M., Havelund, K., Holzmann, G.J., Joshi, R. (eds) NASA Formal Methods. NFM 2011. Lecture Notes in Computer Science, vol 6617. Springer, Berlin, Heidelberg.


Clock synchronization is the foundation of distributed real-time architectures such as the Timed-Triggered Architecture. Maintaining the local clocks synchronized is particularly important for fault tolerance, as it allows one to use simple and effective fault-tolerance algorithms that have been developed in the synchronous system model.

Clock synchronization algorithms have been extensively studied since the 1980s, and many fundamental results have been established. Traditionally, the correctness of a new clock synchronization algorithm is shown by reduction to these results. Until now, formal proofs of correctness all relied on interactive theorem provers such as PVS or Isabelle/HOL. In this paper, we present an automated proof of the TTEthernet clock-synchronization algorithm that is based on the SAL model checker.

Keywords: Model Checker, Formal Proof, Clock Synchronization, Local Clock, Correct Clock

Read more from SRI