uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Handling Global Conditions in Parameterized System Verification
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
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)
Abstract [en]

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
National Category
Computer and Information Science
URN: 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
Available from: 2008-10-17 Created: 2008-10-17 Last updated: 2012-06-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Abdulla, Parosh Aziz
By organisation
Department of Information Technology
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 230 hits
ReferencesLink to record
Permanent link

Direct link