Seventh IEEE International Conference on Engineering of Complex Computer Systems (ICECCS'01)
Compositional Construction of Protocol Behaviours with Arbitrary Channel Capacities
Sk?vde, Sweeden
June 11-June 13
ISBN: 0-7695-1159-7
Abstract: Formal, automated verification methods for parallel systems suffer from the state explosion problem, which prevents analysis of large systems with many components. However, with compositional methods we can sometimes take advantage of regularities in the system structure, enabling verification of even arbitrarily large systems. In this paper we present a case study where we use compositional methods for communication protocol verification. The aim is to determine the externally observable behaviour of protocols that have arbitrarily large (but finite) channel capacities. We construct the behaviour of an example protocol by choosing suitable abstractions and by composing the system in an appropriate order. We also extend the result to protocol families with arbitrary finite numbers of retransmissions. The protocol behaviour thus obtained can be used as a component in any larger system, as well as for verification and visualisation purposes. However, we also show that a similar approach is not possible for the classical alternating bit protocol with reliable or fair channels. Namely, we show that no finite-state invariant can prove that the behaviour is independent of channel capacities.
Index Terms:
verification, parallel systems, protocols, com-positionality, arbitrary channel capacities.
Citation:
Antti Puhakka, "Compositional Construction of Protocol Behaviours with Arbitrary Channel Capacities," iceccs, pp.0080, Seventh IEEE International Conference on Engineering of Complex Computer Systems (ICECCS'01), 2001