# Relaxed Data Types as Consistency Conditions +
## 6 Placing New Consistency Conditions  
We have shown that some data type relaxations can be expressed as consistency conditions. We would like to know how these conditions compare to known consistency conditions. They neither appear to be equivalent to any common consistency conditions, nor do any of our new consistency conditions appear to be related to each other. In this section, we prove that these intuitions are correct. Recall that consistency conditions are just sets of legal schedules [7]. Thus, to compare the strength of different consistency conditions, we can compare the sets of schedules over all data types. Definition 15: Given two consistency conditions \(C\) and \(D\), we say that \(C\) is _stronger_ than \(D\), and \(D\) is _weaker_ than \(C\), if for all data types \(T\), every schedule legal under \(C\) and \(T\) is also legal under \(D\) and \(T\). That is, the set of legal schedules under \(C\), for all data types, is a subset of the set of schedules legal under \(D\). If neither \(C\) is stronger than \(D\) nor \(D\) is stronger than \(C\), we say \(C\) and \(D\) are _incomparable_. If \(C\) is stronger than, but not equal to, \(D\), we say that \(C\) is _strictly stronger_ than \(D\) and \(D\) is _strictly weaker_ than \(C\). Our conditions are in the \"version staleness-based\" family of consistency conditions in [7], referring to the fact that they may return a stale version of the data which is missing some recent updates, since these also have the requirements of Linearizability. Thus, we compare them to \(k\)-Atomicity, \(k\)-Regularity, and \(k\)-Safety, which are also version staleness-based. It is trivial to show that all of our conditions are weaker than Linearizability, since they start with the conditions of Linearizability, then allow some sequences that Linearizability does not. First, we define generalized versions of \(k\)-Regularity and \(k\)-Safety, as we did for \(k\)-Atomicity. Because \(k\)-Regularity and \(k\)-Safety may behave exactly as \(k\)-Atomicity, we have the same restriction to data types without mixed operations. Definition 16 (\(k\)-Regularity): A schedule \(E\) on a data type \(T\) with no mixed operations is \(k\)-regular, for \(k\geq 0\), if there exists a permutation \(\Pi\) of all operation instances in \(E\), respecting the schedule order of non-overlapping instances, such that for every instance \(op\), \(\Pi=\pi.op.p\),  
1. if \(op\) is a mutator or overlaps with no mutator instances, \(\pi|_{m}.op\) is legal by \(k\)-Atomicity; and
2. if \(op\) is an accessor overlapping with at least one other mutator, there exists a sequence \(\pi^{\prime}\) such that \(\pi^{\prime}.op\) is legal in \(T\), where \(\pi^{\prime}\) is constructed either by deleting up to \(k\) instances from the end of \(\pi|_{m}\) or by moving any subset of the mutator instances overlapping with op from after op in \(\Pi\) to before it and placing them in some order._  
**Definition 17** (\(k\)-Safety). : _A schedule \(E\) on a data type \(T\) with no mixed operations is \(k\)-safe, for \(k\geq 0\), if there exists a permutation \(\Pi\) of all operation instances in \(E\), respecting the schedule order of non-overlapping instances, such that for every instance op, \(\Pi=\pi.op.\rho\),_  
1. _if op is a mutator or overlaps with no mutator instances,_ \(\pi|_{m\cdot op}\) _is legal by_ \(k\)_-Atomicity; and_
2. _if op is an accessor overlapping with at least one other mutator, it may return any value in_ \(\text{rets}(OP)\)_._  
First, we state the following theorem relating \(k\)-Atomicity, \(k\)-Regularity, and \(k\)-Safety. This theorem is well established in the literature for registers, and directly generalizes for our new definitions. The proof is by definition, showing each is a strict subset of the previous. **Theorem 5** ([7, 25, 28, 29]).