Communication

In recent software transactional memory proposals, a con-tention manager module is responsible for ensuring that the system as a whole makes progress. A number of con-tention manager algorithms have been proposed and empir-ically 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 trans-actions 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