# Relaxed Data Types as Consistency Conditions +
## 6 Placing New Consistency Conditions
: _For all \(k\geq 0\), \(k\)-Safety is strictly weaker than \(k\)-Regularity which is strictly weaker than \(k\)-Atomicity, which is strictly weaker than \(k\)-Atomicity, which is strictly weaker than Linearizability, in the domain of data types with no mixed operations._  
Theorem 5 claims the following two statements for each pair of consistency conditions \(C\) and \(D\), with \(C\) claimed strictly weaker than \(D\): First, for every data type \(T\) for which \(D\) is defined, every schedule legal under \(D\) and \(T\) is legal under \(C\) and \(T\). Second, there is some data type \(S\) for which there is a schedule legal under \(C\) and \(S\) but not under \(D\) and \(S\). The proof follows immediately from the definitions, since linearizable behavior is legal under \(k\)-Atomicity, \(k\)-atomic behavior is legal under \(k\)-Regularity, and \(k\)-regular behavior is legal under \(k\)-Safety. We next show that none of the three new consistency conditions we have introduced are comparable to any of these three previously known conditions. The naive approach to show that one new consistency condition is incomparable to these three known conditions would require six individual proofs, showing that the new condition neither contains nor is contained by each of the three. We leverage Theorem 5 to reduce this to two steps for each of our consistency conditions:  
1. If we can show that a consistency condition \(C\) does not contain (is not weaker than) \(k\)-Atomicity, then we immediately know that \(C\) is not weaker than either \(k\)-Regularity or \(k\)-Safety. This follows from the fact that, whatever element in \(k\)-Atomicity is not in \(C\) is also in the supersets \(k\)-Regularity and \(k\)-Safety, showing that they are not contained in \(C\). 2. Conversely, if \(k\)-Safety does not contain \(C\), then neither \(k\)-Regularity nor \(k\)-Atomicity can contain \(C\). This is because \(k\)-Regularity and \(k\)-Atomicity are subsets of \(k\)-Safety, and thus also do not contain any element which is not in \(k\)-Safety. Since \(k\)-Safety does not contain \(C\), such an element must exist in \(C\). Thus, we know that \(C\) is not stronger than any of the three. Thus, by Theorem 5, to show a consistency condition \(C\) is incomparable with all of \(k\)-Atomicity, \(k\)-Regularity, and \(k\)-Safety, we choose a data type \(T\) and give a schedule which is legal on \(T\) under \(k\)-Atomicity, but not on \(T\) under \(C\), and a data type \(T^{\prime}\) and give a schedule which is legal on \(T^{\prime}\) under \(C\) but not on \(T^{\prime}\) under \(k\)-Safety. The proof of Theorem 6 uses this structure. **Theorem 6**. : _In the domain of data types which do not have mixed operations,_  
1. _For all_ \(k,l\geq 1\)_,_ \(\text{OutofOrderCC}(k)\) _is incomparable with any of_ \(l\)_-Safety,_ \(l\)_-Regularity, and_ \(l\)_-Atomicity._
2. _For all_ \(k\geq 2\) _and_ \(l\geq 1\)_,_ \(\text{LatenessCC}(k)\) _is incomparable with any of_ \(l\)_-Safety,_ \(l\)_-Regularity, and_ \(l\)_-Atomicity._
3. _For all_ \(k\geq 2\) _and_ \(l\geq 1\)_,_ \(\text{SutteringCC}(k)\) _is incomparable with any of_ \(l\)_-Safety,_ \(l\)_-Regularity, and_ \(l\)_-Atomicity._  
Proof. : Throughout this proof, when we use instances of _Enqueue_ and _Peek_, we are referring to a restricted FIFO queue data type, which has no _Dequeue_, since that is a mixed operation. _Enqueue_ is a pure mutator, since it has no return value, and _Peek_ is a pure accessor, since it does not change the shared object. 1. OutofOrderCC(\(k\)): * To show that OutofOrderCC(\(k\)) does not contain \(l\)-Atomicity, consider the following sequential schedule of a register: \[Write(1).Write(2).Read(1)\] For every \(l\geq 1\), this schedule is legal under \(l\)-Atomicity, since the _Read_ can ignore the presence of the last preceding mutator instance, the \(Write(2)\).