# Relaxed Data Types as Consistency Conditions +
## 6 Placing New Consistency Conditions
This schedule is not legal under OutofOrderCC(\(k\)), for any \(k\geq 1\), as the minimal-length equivalent sequence to \(Write(1).Write(2)\) is simple \(Write(2)\), and \(Read(1)\) is not legal after any sequence obtained by deleting instances from this. * To show that OutofOrderCC(\(k\)) is not contained in \(l\)-Safety, consider the following sequential schedule of a restricted FIFO queue: \[Enqueue(1).Enqueue(2).Peek(2)\] This is legal under OutofOrderCC(\(k\)), for every \(k\geq 1\), as the prefix \(Enqueue(1).Enqueue(2)\) is a minimal-length sequence equivalent to itself, and \(Peek(2)\) is legal after the sequence \(Enqueue(2)\) obtained by removing one mutator instance. This schedule is not legal under \(l\)-Safety, for any \(l\geq 1\), since none of the instances are concurrent, and \(Peek(2)\) is not legal after any sequence obtained by deleting consecutive mutators from the end of the preceding sequence. Thus, OutofOrderCC(\(k\)) is not a subset of \(l\)-Safety and is thus not stronger than any of \(l\)-Safety, \(l\)-Regularity, and \(l\)-Atomicity. 2. LatenessCC(\(k\)): * Consider this sequential schedule of a register: \[Write(1).Write(2).Read(1)\] This schedule is legal under \(l\)-Atomicity, for \(l\geq 1\), since the first two instances are legal in a register, and the \(Read(1)\) is legal after the sequence obtained by ignoring the last previous mutator. This schedule is not legal under LatenessCC(\(k\)), \(k\geq 2\), since the minimal-length equivalent sequence of \(Write(1).Write(2)\) is \(Write(2)\), so \(Read(1)\) is not legal after any sequence obtained by deleting instances from a minimal sequence equivalent to the sequence of preceding instances. * Consider the following sequential schedule of a restricted FIFO queue: \[Enqueue(1).Enqueue(2).Peek(2)\] This schedule is legal under LatenessCC(\(k\)), for \(k\geq 2\), since \(Enqueue(1).Enqueue(2)\) is legal in a FIFO queue and \(Peek(2)\) is legal after the sequence \(Enqueue(2)\) obtained by removing one instance, which is allowed because \(Enqueue(1).Enqueue(2)\) is a minimal-length equivalent sequence of itself. This schedule is not legal under \(l\)-Safety, for any \(l\geq 1\), because \(Peek(2)\) is not concurrent with any mutator and not legal after any sequence obtained by deleting instances from the end of \(Enqueue(1).Enqueue(2)\). 3. StutteringCC(\(k\)):
* Consider the following sequential schedule of a register: \[Write(1).Write(2).Read(1).Read(2)\] This schedule is legal under \(l\)-Atomicity, \(l\geq 1\), since the first \(Read\) instance may ignore the last previous mutator, while the second \(Read\) may see it. For \(k\geq 2\), this schedule is not legal under StutteringCC(\(k\)), as the first \(Read\) may only return 1 if \(Write(2)\) stuttered, but then no succeeding \(Read\) can see the \(Write(2)\). * Consider the following sequential schedule of a restricted FIFO queue: \[Enqueue(1).Enqueue(2)...Enqueue(k-1).Enqueue(k)...Enqueue(k+l).Peek(k)\] This schedule is legal under StutteringCC(\(k\)), \(k\geq 2\) (Recall that StutteringCC(\(1\)) is merely Linearizability), since the first \(k-1\)\(Enqueue\) instances may stutter, leaving \(Peek(k)\) legal after the prefix \(Enqueue(k)...Enqueue(k+l)\). This schedule is not legal under \(l\)-Safety, \(l\geq 1\), since the \(Peek\) is not concurrent with any mutator and ignoring up to \(l\) of the last previous mutators will not allow \(Peek\) to return any value besides 1. While our new consistency conditions are all incomparable to these similar existing conditions in general, we observe that for some specific data types, they may not actually be distinct. We next show that, for a certain class of data types, StutteringCC(\(k\)) is stronger than \(k\)-Atomicity. We actually show that StutteringCC(\(k\)) is stronger than \((k-1)\)-Atomicity, a special case of, and thus stronger than, \(k\)-Atomicity. This class of types contains those where all mutators are _overwriters_.