A simple deterministic algorithm for guaranteeing the forward progress of transactions

• 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.

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.”