Verification of semantic commutativity conditions and inverse operations on linked data structures
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2012
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/68502 |
| _version_ | 1811082681552732160 |
|---|---|
| author | Kim, Deokhwan, Ph. D. Massachusetts Institute of Technology. |
| author2 | Martin C. Rinard. |
| author_facet | Martin C. Rinard. Kim, Deokhwan, Ph. D. Massachusetts Institute of Technology. |
| author_sort | Kim, Deokhwan, Ph. D. Massachusetts Institute of Technology. |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011. |
| first_indexed | 2024-09-23T12:07:15Z |
| format | Thesis |
| id | mit-1721.1/68502 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:07:15Z |
| publishDate | 2012 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/685022020-03-31T14:44:51Z Verification of semantic commutativity conditions and inverse operations on linked data structures Kim, Deokhwan, Ph. D. Massachusetts Institute of Technology. Martin C. Rinard. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011. Cataloged from PDF version of thesis. Includes bibliographical references (p. 57-61). We present a new technique for verifying commutativity conditions, which are logical formulas that characterize when operations commute. Because our technique reasons with the abstract state of verified linked data structure implementations, it can verify commuting operations that produce semantically equivalent (but not necessarily identical) data structure states in different execution orders. We have used this technique to verify sound and complete commutativity conditions for all pairs of operations on a collection of linked data structure implementations, including data structures that export a set interface (ListSet and HashSet) as well as data structures that export a map interface (AssociationList, HashTable, and ArrayList). This effort involved the specification and verification of 765 commutativity conditions. Many speculative parallel systems need to undo the effects of speculatively executed operations. Inverse operations, which undo these effects, are often more efficient than alternate approaches (such as saving and restoring data structure state). We present a new technique for verifying such inverse operations. We have specified and verified, for all of our linked data structure implementations, an inverse operation for every operation that changes the data structure state. Together, the commutativity conditions and inverse operations provide a key resource that language designers, developers of program analysis systems, and implementors of software systems can draw on to build languages, program analyses, and systems with strong correctness guarantees. by Deokhwan Kim. S.M. 2012-01-12T19:32:49Z 2012-01-12T19:32:49Z 2011 2011 Thesis http://hdl.handle.net/1721.1/68502 770673527 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 61 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Kim, Deokhwan, Ph. D. Massachusetts Institute of Technology. Verification of semantic commutativity conditions and inverse operations on linked data structures |
| title | Verification of semantic commutativity conditions and inverse operations on linked data structures |
| title_full | Verification of semantic commutativity conditions and inverse operations on linked data structures |
| title_fullStr | Verification of semantic commutativity conditions and inverse operations on linked data structures |
| title_full_unstemmed | Verification of semantic commutativity conditions and inverse operations on linked data structures |
| title_short | Verification of semantic commutativity conditions and inverse operations on linked data structures |
| title_sort | verification of semantic commutativity conditions and inverse operations on linked data structures |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/68502 |
| work_keys_str_mv | AT kimdeokhwanphdmassachusettsinstituteoftechnology verificationofsemanticcommutativityconditionsandinverseoperationsonlinkeddatastructures |