Pérez, JAN; Rybalchenko, A; Singh, A; (2009) Cardinality Abstraction for Declarative Networking Applications. In: Bouajjani, A and Maler, O, (eds.) Computer Aided Verification. 21st International Conference, CAV 2009, Grenoble, France, June 26 - July 2, 2009. Proceedings. (pp. 584 - 598). Springer Berlin Heidelberg

Preview

PDF Navarro_cav09.pdf Download (226kB)

Abstract

Declarative Networking is a recent, viable approach to make distributed programming easier, which is becoming increasingly popular in systems and networking community. It offers the programmer a declarative, rule-based language, called P2, for writing distributed applications in an abstract, yet expressive way. This approach, however, imposes new challenges on analysis and verification methods when they are applied to P2 programs. Reasoning about P2 computations is beyond the scope of existing tools since it requires handling of program states defined in terms of collections of relations, which store the application data, together with multisets of tuples, which represent communication events in-flight. In this paper, we propose a cardinality abstraction technique that can be used to analyze and verify P2 programs. It keeps track of the size of relations (together with projections thereof) and multisets defining P2 states, and provides an appropriate treatment of declarative operations, e.g., indexing, unification, variable binding, and negation. Our cardinality abstraction-based verifier successfully proves critical safety properties of a P2 implementation of the Byzantine fault tolerance protocol Zyzzyva, which is a representative and complex declarative networking application.

Download activity - last month

Export as JSONXMLCSV

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as CSVJSONXML

Archive Staff Only

View Item