A simple deterministic algorithm for guaranteeing the forward progress of transactions
This paper describes a remarkably simple deterministic (not probabilistic) contention-management algorithm for guaranteeing the forward progress of transactions - avoiding deadlocks, livelocks, and other anomalies. The transactions must be finite (no infinite loops), but on each restart, a transacti...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Elsevier
2018
|
| Online Access: | http://hdl.handle.net/1721.1/114871 https://orcid.org/0000-0001-6386-5552 |
| _version_ | 1826189885815390208 |
|---|---|
| author | Leiserson, Charles E |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Leiserson, Charles E |
| author_sort | Leiserson, Charles E |
| collection | MIT |
| description | This paper describes a remarkably simple deterministic (not probabilistic) contention-management algorithm for guaranteeing the forward progress of transactions - avoiding deadlocks, livelocks, and other anomalies. The transactions must be finite (no infinite loops), but on each restart, a transaction may access different shared-memory locations. The algorithm supports irrevocable transactions as long as the transaction satisfies a simple ordering constraint. In particular, a transaction that accesses only one shared-memory location is never aborted. The algorithm is suitable for both hardware and software transactional-memory systems. It also can be used in some contexts as a locking protocol for implementing transactions "by hand.". |
| first_indexed | 2024-09-23T08:27:25Z |
| format | Article |
| id | mit-1721.1/114871 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:27:25Z |
| publishDate | 2018 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/1148712022-09-23T12:42:38Z A simple deterministic algorithm for guaranteeing the forward progress of transactions Leiserson, Charles E Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Leiserson, Charles E This paper describes a remarkably simple deterministic (not probabilistic) contention-management algorithm for guaranteeing the forward progress of transactions - avoiding deadlocks, livelocks, and other anomalies. The transactions must be finite (no infinite loops), but on each restart, a transaction may access different shared-memory locations. The algorithm supports irrevocable transactions as long as the transaction satisfies a simple ordering constraint. In particular, a transaction that accesses only one shared-memory location is never aborted. The algorithm is suitable for both hardware and software transactional-memory systems. It also can be used in some contexts as a locking protocol for implementing transactions "by hand.". 2018-04-23T16:54:56Z 2018-04-23T16:54:56Z 2015-12 2015-10 2018-04-19T19:31:04Z Article http://purl.org/eprint/type/JournalArticle 0306-4379 http://hdl.handle.net/1721.1/114871 Leiserson, Charles E. “A Simple Deterministic Algorithm for Guaranteeing the Forward Progress of Transactions.” Information Systems 57 (April 2016): 69–74 © 2016 Published by Elsevier Ltd https://orcid.org/0000-0001-6386-5552 http://dx.doi.org/10.1016/J.IS.2015.10.013 Information Systems Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier Other univ. web domain |
| spellingShingle | Leiserson, Charles E A simple deterministic algorithm for guaranteeing the forward progress of transactions |
| title | A simple deterministic algorithm for guaranteeing the forward progress of transactions |
| title_full | A simple deterministic algorithm for guaranteeing the forward progress of transactions |
| title_fullStr | A simple deterministic algorithm for guaranteeing the forward progress of transactions |
| title_full_unstemmed | A simple deterministic algorithm for guaranteeing the forward progress of transactions |
| title_short | A simple deterministic algorithm for guaranteeing the forward progress of transactions |
| title_sort | simple deterministic algorithm for guaranteeing the forward progress of transactions |
| url | http://hdl.handle.net/1721.1/114871 https://orcid.org/0000-0001-6386-5552 |
| work_keys_str_mv | AT leisersoncharlese asimpledeterministicalgorithmforguaranteeingtheforwardprogressoftransactions AT leisersoncharlese simpledeterministicalgorithmforguaranteeingtheforwardprogressoftransactions |