Towards Verification of the Pastry Protocol Using TLA + 

Abstract : Pastry is an algorithm that provides a scalable distributed hash table over an underlying P2P network. Several implementations of Pastry are available and have been applied in practice, but no attempt has so far been made to formally describe the algorithm or to verify its properties. Since Pastry combines rather complex data structures, asynchronous communication, concurrency, resilience to churn and fault tolerance, it makes an interesting target for verification. We have modeled Pastry’s core routing algorithms and communication protocol in the specification language TLA + . In order to validate the model and to search for bugs we employed the TLA +  model checker tlc to analyze several qualitative properties. We obtained non-trivial insights in the behavior of Pastry through the model checking analysis. Furthermore, we started to verify Pastry using the very same model and the interactive theorem prover tlaps for TLA + . A first result is the reduction of global Pastry correctness properties to invariants of the underlying data structures.
Type de document :
Communication dans un congrès
Roberto Bruni; Juergen Dingel. 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik, Iceland. Springer, Lecture Notes in Computer Science, LNCS-6722, pp.244-258, 2011, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-21461-5_16〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01583322
Contributeur : Hal Ifip <>
Soumis le : jeudi 7 septembre 2017 - 11:10:21
Dernière modification le : jeudi 11 janvier 2018 - 06:23:13

Fichier

978-3-642-21461-5_16_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Tianxiang Lu, Stephan Merz, Christoph Weidenbach. Towards Verification of the Pastry Protocol Using TLA + . Roberto Bruni; Juergen Dingel. 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik, Iceland. Springer, Lecture Notes in Computer Science, LNCS-6722, pp.244-258, 2011, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-21461-5_16〉. 〈hal-01583322〉

Partager

Métriques

Consultations de la notice

111

Téléchargements de fichiers

9