DROPS

Document

09361 Abstracts Collection – Design and Validation of Concurrent Systems

Authors: Cormac Flanagan, Susanne Graf, Madhusan Parthasarathy, and Shaz Quadeer

Published in: Dagstuhl Seminar Proceedings, Volume 9361, Design and Validation of Concurrent Systems (2010)

Abstract

The Dagstuhl Seminar 09361 ``Design and Validation of Concurrent Systems'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics from August 30 to September 4, 2009. During the seminar, participants presented their current research, and ongoing work and open problems were discussed. This paper reviews the seminar topics and goals, and provides abstracts of the presentations given during the seminar. Links to extended abstracts or full papers are provided, if available.

Cite as

Cormac Flanagan, Susanne Graf, Madhusan Parthasarathy, and Shaz Quadeer. 09361 Abstracts Collection – Design and Validation of Concurrent Systems. In Design and Validation of Concurrent Systems. Dagstuhl Seminar Proceedings, Volume 9361, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{flanagan_et_al:DagSemProc.09361.1,
  author =	{Flanagan, Cormac and Graf, Susanne and Parthasarathy, Madhusan and Quadeer, Shaz},
  title =	{{09361 Abstracts Collection – Design and Validation of Concurrent Systems}},
  booktitle =	{Design and Validation of Concurrent Systems},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9361},
  editor =	{Cormac Flanagan and Madhusan Parthasarathy and Shaz Quadeer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09361.1},
  URN =		{urn:nbn:de:0030-drops-25498},
  doi =		{10.4230/DagSemProc.09361.1},
  annote =	{Keywords: Concurrency, Specification, Programming, Verification, Validation, Testing}
}

Document

DOI: 10.4230/DagSemProc.09361.2

Verifying Optimistic Concurrency: Prophecy Variables and Backward Reasoning

Authors: Serdar Tasiran, Ali Sezgin, and Shaz Quadeer

Published in: Dagstuhl Seminar Proceedings, Volume 9361, Design and Validation of Concurrent Systems (2010)

Abstract

Several static proof systems have been developed over the years for verifying shared-memory multithreaded programs. These proof systems make use of auxiliary variables to express mutual exclusion or non-interference among shared variable accesses. Typically, the values of these variables summarize the past of the program execution; consequently, they are known as history variables. Prophecy variables, on the other hand, are the temporal dual of history variables and their values summarize the future of the program execution. In this paper, we show that prophecy variables are useful for locally constructing proofs of systems with optimistic concurrency. To enable the fullest use of prophecy variables in proof construction, we introduce tressa annotations, as the dual of the well-known assert annotations. A tressa claim states a condition for reverse reachability from an end state of the program, much like an assert claim states a condition for forward reachability from the initial state of the program. We present the proof rules and the notion of correctness of a program for two-way reasoning in a static setting: forward in time for assert claims, backward in time for tressa claims. Even though the interaction between the two is non-trivial, the formalization is intuitive and accessible. We demonstrate how to verify implementations based on optimistic concurrency which is a programming paradigm that allows conflicts to be handled after they occur. We have incorporated our proof rules into the QED verifier and have used our implementation to verify a handful of small but sophisticated algorithms. Our experience shows that the proof steps and annotations follow closely the intuition of the programmer, making the proof itself a natural extension of implementation.

Cite as

Serdar Tasiran, Ali Sezgin, and Shaz Quadeer. Verifying Optimistic Concurrency: Prophecy Variables and Backward Reasoning. In Design and Validation of Concurrent Systems. Dagstuhl Seminar Proceedings, Volume 9361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{tasiran_et_al:DagSemProc.09361.2,
  author =	{Tasiran, Serdar and Sezgin, Ali and Quadeer, Shaz},
  title =	{{Verifying Optimistic Concurrency: Prophecy Variables and Backward Reasoning}},
  booktitle =	{Design and Validation of Concurrent Systems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9361},
  editor =	{Cormac Flanagan and Madhusan Parthasarathy and Shaz Quadeer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09361.2},
  URN =		{urn:nbn:de:0030-drops-24306},
  doi =		{10.4230/DagSemProc.09361.2},
  annote =	{Keywords: Concurrency, Program Verification, Static Analysis}
}

Search Results

Documents authored by Quadeer, Shaz

09361 Abstracts Collection – Design and Validation of Concurrent Systems

Abstract

Cite as

Verifying Optimistic Concurrency: Prophecy Variables and Backward Reasoning

Abstract

Cite as

Thanks for your feedback!

Could not send message