Toward a Theory of Input Acceptance for Transactional Memories

As opposed to database transactional systems, transactional memory (TM) systems are constrained by real-time while treating their input workload. Nevertheless, there is no clear formalization of how a TM should react regarding to a specific input. While TM performance is often measured in terms of throughput, i.e., commit-rate (by time unit), we consider the commit-abort ratio of a TM for a given input, as the number of transactions this TM commits over the total number of input transactions. Building onto this, this paper defines the input acceptance of TMs depending on their commit-abort ratio on input classes. To this end, we exhibit several classes of workloads and identify bounds on the input acceptance of existing TM designs. Additionally, we propose a serializable STM that presents high input acceptance at the cost of a more complex algorithm than existing STMs. Finally, experimental validation compares the presented TM designs in terms of input acceptance with realistic workloads.