Handling Global Conditions in Parameterized System Verification
1999 (English)In: Proc. 11th Int. Conf. on Computer Aided Verification / [ed] Nicolas Halbwachs, Doron Peled, Berlin: Springer Verlag , 1999, 134-145 p.Conference paper (Refereed)
We consider symbolic verification for a class of parameterized systems, where a system consists of a linear array of processes, and where an action of a process may in general be guarded by both local conditions restricting the state of the process about to perform the action, and global conditions defining the context in which the action is enabled. Such actions are present, e.g., in idealized versions of mutual exclusion protocols, such as the bakery and ticket algorithms by Lamport, Burn’s protocol, Dijkstra’s algorithm, and Szymanski’s algorithm. The presence of both local and global conditions makes the parameterized versions of these protocols infeasible to analyze fully automatically, using existing model checking methods for parameterized systems. In all these methods the actions are guarded only by local conditions involving the states of a finite set of processes. We perform verification using a standard symbolic reachability algorithm enhanced by an operation to accelerate the search of the state space. The acceleration operation computes the effect of an arbitrary number of applications of an action, rather than a single application. This is crucial for convergence of the analysis e.g. when applying the algorithm to the above protocols. We illustrate the use of our method through an application to Szymanski’s algorithm.
Place, publisher, year, edition, pages
Berlin: Springer Verlag , 1999. 134-145 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 1633
Computer and Information Science
IdentifiersURN: urn:nbn:se:uu:diva-40386DOI: 10.1007/3-540-48683-6_14ISBN: 3540662022OAI: oai:DiVA.org:uu-40386DiVA: diva2:68287
Computer aided verification : 11th international conference ; CAV '99, Trento, Italy, July 6 - 10, 1999