Online Algorithms for Scheduling Transactions on Python Software Transactional Memory

Abstract

Designing online transaction scheduling algorithms is challenging because one needs to reconcile three opposing requirements: (i) they should be fast, (ii) they should minimize makespan and maximize throughput, and (iii) they should produce conflict-free transaction schedules. In this paper we present four online transaction scheduling algorithms, namely, RR, ETLB, AC, and AAC algorithm, we prove their correctness and time bounds, and we conduct a theoretical analysis of the transaction schedules they produce, using three different workloads (RDW, CFW, and WDW). Finally, we compare various features of the four algorithms. The results are as expected, as we go from RR, over ETLB and AC, to AAC algorithms, the quality of the resulting schedules increases at the cost of increase of algorithm’s time complexity.