Toward a Theory of Transactional Contention Managers

In recent software transactional memory proposals, a contention manager module is responsible for ensuring that the system as a whole makes progress. A number of contention manager algorithms have been proposed and empirically evaluated. In this paper we lay some foundations for a theory of contention management. We present the greedy contention manager, the first to combine non-trivial provable properties with good practical performance. In a model where transaction delays are finite, the greedy manager guarantees that every transaction commits within a bounded time, and the time to complete n concurrent normalized (i.e., of equal duration) transactions that share s objects is within a factor of s(s + 1) + 2 of the time that would have been taken by an optimal off-line list scheduler. No contention manager reviewed in the literature satisfies both the properties. Benchmark results convey our claim of the practicality of the greedy manager.