# Relaxed Data Types as Consistency Conditions +
Footnote †: This paper is an extended version of our paper published in19 th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). [PERSON] *  
requires that all operations on shared data appear to all processes as if they happened sequentially, in an order respecting the order of operations which do not overlap in real time. This makes program design and reasoning about program correctness relatively easy, as we are familiar with sequential program design and analysis. However, Linearizability is generally expensive to implement, in terms of computation and communication delays. For example, [PERSON] et al. [2] showed that it is impossible to linearizably implement many common data types without expensive synchronization steps; [PERSON] and [PERSON] [3] showed that Linearizability is necessarily more expensive than sequential consistency; [PERSON] and [PERSON] [4] showed that requiring even a consistency weaker than Linearizability is expensive; and [PERSON] et al. [5] and [PERSON] and [PERSON] [6] showed lower bounds on the worst-case and amortized cost of certain operations under Linearizability. To avoid this cost, many weaker consistency conditions have been proposed (see [PERSON] and [PERSON] [7] for a review of consistency conditions in the literature), allowing more concurrent executions while providing weaker guarantees on the behavior of shared objects. Under these conditions, data types can be implemented more efficiently in terms of operation response time than they can under Linearizability (e.g., [3]). Some work has been done to explore classes of data types which, when implemented under a weak consistency condition, give stronger behavioral guarantees than those of the consistency condition (e.g., [8]). Another approach for increasing the efficiency of distributed data type implementations that has recently gained popularity is to _relax_ the sequential specification of the data type. [PERSON] et al. [9] defined a weak consistency condition in a manner similar to how we consider relaxations. [PERSON] et al. [10] formalized and generalized the notion of relaxations. Several papers have implemented a variety of relaxed data types (e.g., [11]). By allowing some specific behaviors that were otherwise illegal, particularly by allowing non-deterministic choices between possible behaviors, several papers have shown both empirically and formally that it is possible to reduce the (amortized) implementation costs of data types [6; 10; 12; 13; 14]. This does come at some cost to the computational strength of the implemented data type [15; 16]. Proposed applications for relaxed data types include relaxed sets as work-stealing queues [17], counters that miss some increments but are statistically useful [9], and relaxed queues for webserver request handling [18]. Data type relaxations are generally (to date) implemented under Linearizability, so all new behaviors are specified sequentially. Sequential behaviors are often easier to understand, and thus use correctly, than complex conditions on concurrent executions, which are hard to visualize. In this paper, we explore the relation of these two different methods for improving the performance of shared data type implementations. We show that the combination of Linearizability and three data type relaxations common in the literature, \(k\)-Out-of-Order, \(k\)-Lateness, and \(k\)-Stuttering [10], can be alternately defined as consistency conditions. That is, the set of concurrent executions which are considered legal under Linearizability when working with the relaxed type is the same as the set of concurrent executions which are legal under the new consistency condition and the original, unrelaxed type. Conversely, we show, with the example of \(k\)-Atomicity, that some consistency conditions can be separated into Linearizability and a sequential data type relaxation.