Conflict Avoidance: Data Structures in Transactional Memory

The Dynamic Software Transactional Memory system lets multiple threads safely access data through atomic transactions. Conflicts between transactions require one to abort, incurring a high performance cost. By managing the likelihood that actions will produce conflicts, data struc-ture design greatly impacts the efficiency of transactional programs. I analyze a red-black tree and a binomial heap, using both the classic al-gorithms and delayed-rebalancing versions which enclose the rebalancing step in a separate transaction. Delaying the rebalancing step of these structures dramatically improves their performance by minimizing over-lapping claims to transactional objects.