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