Title: Compositional construction of protocol behaviours with arbitrary channel capacities
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 ...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. The article presents 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.Read More
Publication Year: 2002
Publication Date: 2002-11-13
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot