A simple deterministic algorithm for guaranteeing the forward progress of transactions. (April 2016)

• Record Type: Journal Article
• Authors: Leiserson, Charles E.
• Is Part Of: Information systems. Volume 57(2016)
• Page Start: 69
• Page End: 74
• Publication Date: 2016-04
• Subjects: Algorithm -- Contention manager -- Deadlock -- Forward progress -- Mutual exclusion -- Ownership array -- Proof -- Synchronization -- Transaction; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2015.10.013
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: 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." Abstract : Highlights: A remarkably simple algorithm can guarantee the forward progress of transactions. The algorithm supports irrevocable transactions. The algorithm is suitable for hardware or software transactional-memory systems. The algorithm can be used as a locking protocol.