# Adaptive Versioning in Transactional Memory Systems +
## 4 Basic Adaptive Versioning
### High Level Overview  
The high level idea in Adaptive is to switch the versioning method depending on performance. That is, if the versioning method currently used is hampering the performance, then switch the versioning to improve the performance. The fundamental question is how to identify and measure an indicator that reflects appropriately the effect of the versioning method on performance. Fortunately, in TM systems, if the number of aborts are increasing compared to the number of commits, then it is be a valid indicator of performance degradation due to the versioning method currently in use. Therefore, we pick abort to commit ratio (ACR) as a performance indicator. ACR has also been used quite heavily in the TM literature as a vital indicator of performance, for example, see [69].  
Formally, ACR can be defined at any time \(t>0\) as follows:  
\[ACR=\frac{N_{abort}}{N_{commit}}, \tag{1}\]  
where \(N_{abort}\) is the total number of aborted transactions and \(N_{commit}\) is the total number of committed transactions from time \(0\) up to \(t\). Ideally, the goal is to have no aborts, i.e., \(ACR=0\). However, in practice, this may not be feasible and the goal is to minimize ACR as much as possible.  
Let \(T\) be a transaction that comes to the system at time \(t\geq 0\); we assume that the execution starts at time \(t_{0}=0\). Let \(N_{Ecommit}(N_{Lcommit})\) be the number of transaction commits in Adaptive from time \(t_{0}=0\) until the current time \(t>t_{0}\) executed using eager (lazy) versioning. Similarly, let \(N_{Eabort}(N_{Labort})\) be the total number of transaction aborts in Adaptive from time \(t_{0}=0\) until time \(t>t_{0}\) executed using eager (lazy) versioning. Furthermore, let \(N_{commit}\) and \(N_{abort}\) be the total number of commits and aborts in Adaptive from \(t_{0}=0\) until time \(t>t_{0}\). Notice that  
\[N_{commit}=N_{Ecommit}+N_{Lcommit}\]  
and  
\[N_{abort}=N_{Eabort}+N_{Labort}.\]  
The concept in Adaptive is to decide on which versioning method to use for executing \(T\) based on the parameters \(N_{Ecommit}\), \(N_{Lcommit}\), \(N_{Eabort}\), and \(N_{Labort}\) learned from the system at runtime. However, if \(T\) comes to the system at time \(t_{0}=0\), we have all \(N_{Ecommit}\), \(N_{Lcommit}\), \(N_{Eabort}\), and \(N_{Labort}\) zero. We treat this as a special case. In the special case of \(t_{0}=0\), a simple approach is to execute \(T\) using either lazy or eager versioning. However, if some information regarding the workload is available, then we can decide on which versioning method to use. Suppose, the read and write sets of \(T\) are available. Let \(\mathit{Wset}(T)\) be the _write set_ of \(T\) which is essentially the memory locations that \(T\) would modify while executing. Similarly, let \(\mathit{Rset}(T)\) be the _read set_ of \(T\) which is essentially the memory locations that \(T\) would read (but not modify) while executing. \(RW(T)=\mathit{Rset}(T)+\mathit{Wset}(T)\), where \(RW(T)\) denotes the total number of memory locations that \(T\) reads and modifies while executing. If \(|\mathit{Wset}(T)|>|\mathit{Rset}(T)|\), then \(T\) is executed using lazy versioning, otherwise using eager versioning.  
For any transaction \(T\) arriving at time \(t>t_{0}\), we have two different models of Adaptive described in the following sub-sections, one for persistent memories and another for non-persistent memories.