About This Item

Ask the MINDS@UW Librarian

A Decision Procedure for Detecting Atomicity Violations for Communicating Processes with Locks

Show full item record


Kidd, Nicholas; Lammich, Peter; Touili, Tayssir; Reps, Thomas
University of Wisconsin-Madison Department of Computer Sciences
Mar 15, 2012
We present a new decision procedure for detecting property violations in pushdown models for concurrent programs that use lock-based synchronization, where each thread's lock operations are properly nested (a la synchronized methods in Java). The technique detects violations expressed as indexed phase automata (PAs)|a class of non-deterministic nite automata in which the only loops are self-loops. Our interest in PAs stems from their ability to capture atomic-set serializability violations. (Atomic-set serializability is a relaxation of atomicity to only a user-specified set of memory locations.) We implemented the decision procedure and applied it to detecting atomic-set-serializability violations in models of concurrent Java programs. Compared with a prior method based on a semi-decision procedure, not only was the decision procedure 7.5X faster overall, but the semi-decision procedure timed out on about 68% of the queries versus 4% for the decision procedure.
Permanent link
Export to RefWorks 

Part of

Show full item record

Search and browse


Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.