# Relaxed Data Types as Consistency Conditions +
## 4 Converting Relaxations to Consistency Conditions  
Relaxing data types and weakening consistency conditions have so far been largely separate methods of improving the performance of shared data types. In the next two sections, we show by example that some relaxed data types under Linearizability can be equivalently defined as their base types under weaker consistency conditions and vice versa. The basic idea is to think of both consistency conditions and relaxations as functions. A consistency condition reduces concurrent schedules to one or more sequences of operation instances, which can be compared to the legal sequences of a given data type. We can view this as a function from the space of possible concurrent schedules to the power set of possible operation instance sequences. A data type relaxation takes a sequence of operation instances and transforms it to a sequence legal in the base type. This is a function from the space of possible operation instance sequences to itself. Since the codomain of consistency conditions is sets of elements of the domain of relaxations, we can compose the two \"functions\". The consistency condition can map a concurrent schedule to sequences that may not be legal by the base type, but then we may transform them by the rules of a relaxation to be legal. Thus, both collapsing concurrency and allowing some variance from the base set of legal sequences can occur in the consistency condition. Similarly, if a consistency condition requires a global ordering respecting the schedule order, then adds other conditions, we show in Section 5 that we can split these conditions apart to have Linearizability for the consistency condition and a relaxation of the original data type, while still allowing the same set of concurrent schedules. We will start by defining several consistency conditions which are equivalent to the data type relaxations introduced in Section 3. For each, the set of linearizable schedules legal for the relaxed version of a data type is equal to the set of schedules legal for the original data type and the weaker consistency condition. First, we discuss the Out-of-Order relaxation. This enables operations to return values which are not legal by the specification of the base type \(T\), but would be legal if a few other instances had not occurred. **Definition 10** (OutofOrderCC\((k)\)). : _A schedule of any ADT \(T\) satisfies OutofOrderCC\((k)\), for an integer \(k\geq 0\), if_  
1. _There exists a permutation_ \(\Pi\) _of all operation instances in the schedule, which respects the schedule order of non-overlapping instances._
2. _For every_ \(op\in\Pi\)_, with_ \(\Pi=\pi.op.\rho\)_, there is some sequence_ \(u.v.w\)_,_ \(|v|\leq k\)_, which is a minimum-length sequence equivalent in_ \(T\) _to_ \(\pi\)_, and there exists a sequence_ \(x\)_, such that:_ 1. \(u.w\) _is legal in_ \(T\) _and minimum-length among the set of sequences equivalent to it in_ \(T\)_;_ 2. \(u.w.op\) _is legal in_ \(T\)_; and_ 3. \(u.\) _\(u.w.op\equiv x.w\) _and_ \(\pi.op\equiv x.v.w\)_, or_ 4. \(u.w.op\equiv u.x\) _and_ \(\pi.op\equiv u.v.x\)_._  
**Theorem 1**. : _For any integer \(k\geq 0\), the set of schedules legal on a \(k\)-Out-of-Order relaxation of any ADT \(T\) under Linearizability is the same as the set of schedules legal on \(T\) under OutofOrderCC\((k)\)._  
We can similarly define consistency conditions LatenessCC\((k)\) and StutteringCC\((k)\) equivalent to \(k\)-Lateness and \(k\)-Stuttering relaxed versions of a type \(T\) under Linearizability. By rolling the relaxation into the consistency condition, it follows that the schedules legal on these relaxed data types under Linearizability are those legal on the base type under a weaker consistency condition. Theorems 1, 2, and 3 all hold by construction. **Definition 11** (LatenessCC\((k)\)). : _A schedule of any ADT \(T\) satisfies LatenessCC\((k)\), for an integer \(k\geq 1\), if_  
1.