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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1633
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:uu:diva-40386DOI: 10.1007/3-540-48683-6_14ISBN: 3540662022 (print)OAI: oai:DiVA.org:uu-40386DiVA: diva2:68287
Conference
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

Authority records BETA

Abdulla, Parosh Aziz

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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 456 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf