2015/10/23 by Anshu S. Anand, Anshu S Anand, R. K. Shyamasundar +5
Computer Science · Psychology · #Cognitive Functions and Memory #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Security and Verification in Computing #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1510.06967
arXiv admin note: text overlap with arXiv:1307.8256
arxiv created 2015/10/23 · openalex publication_date 2015/10/23 · arxiv updated 2015/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we describe an enhanced Automatic Check- pointing and Partial Rollback algorithm(CaP R + ) to realize Software Transactional Memory(STM) that is based on con- tinuous conflict detection, lazy versioning with automatic checkpointing, and partial rollback. Further, we provide a proof of correctness of CaP R+ algorithm, in particular, Opacity, a STM correctness criterion, that precisely captures the intuitive correctness guarantees required of transactional memories. The algorithm provides a natural way to realize a hybrid system of pure aborts and partial rollbacks. We have also implemented the algorithm, and shown its effectiveness with reference to the Red-black tree micro-benchmark and STAMP benchmarks. The results obtained demonstrate the effectiveness of the Partial Rollback mechanism over pure abort mechanisms, particularly in applications consisting of large transaction lengths.