loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Antti Puhakka, Tampere University of Technology
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
Usage of this product signifies your acceptance of the Terms of Use.