On Maintaining Multiple Versions in STM
An effective way to reduce the number of aborts in Software Transactional Memory (STM) is to keep multiple versions of transactional objects. In this paper, the authors study inherent properties of STMs that use multiple versions to guarantee successful commits of all read-only transactions. They first show that these STMs cannot be disjoint-access parallel. They then consider the problem of garbage collecting old object versions, and show that no STM can be optimal in the number of previous versions kept. Moreover, they show that garbage collecting useless versions is impossible in STMs that implement invisible reads. Finally, they present an STM algorithm using visible reads that efficiently garbage collects useless object versions.