D.1.1 – Survey on Weak Consistency Approaches for Large-Scale Systems

GDD_HCERES2020Distributed systems are often viewed as more difficult to program than sequential systems be- cause they require solving a number of communication issues. Shared objects that can be accessed concurrently by multiple parties can be used as a practical communication abstraction to let pro- cesses enjoy a more general view of the system. A precise specification of these objects is therefore essential to ensure their adoption as well as the reliability of distributed systems.Many models have been proposed to specify shared memory, and several inventories [Mos93, AG96] can be found in the literature. In [Lam86], Lamport defines linearizable registers that ensure that everything appears as if all the operation where executed instantaneously at a point between the moment when the operation is called and the moment when it returns. Sequential consistency [Lam79] is a little weaker: it only guarantees that all the operations appear as totally ordered, and that this order be compatible with the program order, the order in which each process performs its own operations.These strong consistency criteria are very expensive to implement in message-passing systems. In terms of latency, it is necessary to wait for answers for the reads or the writes for sequential consistency [LS88] and for all kinds of operations in the case of linearizability [AW94]. In terms of fault tolerance, strong hypotheses must be respected by the system: it is impossible to resist to partitioning [Bre00, GL02]. Many weaker consistency criteria have been proposed to solve this problem. Among them, PRAM [LS88], causal memory [ANB+95] and eventual consistency [Vog08] are best documented. PRAM is a local consistency criterion: each process only sees its own reads and all the writes, and all these operations appear to it as totally ordered by an order that respects the program order. Causal consistency strengthens PRAM by imposing to these total orders to be compatible with a partial order that is common to all processes, the causal order, that not only contains the process order, but also a writes-into relation, that encodes data dependencies between the write and the read operations. Eventual consistency expects that, if all the processes stop writing, they will eventually read the same values.Memory is a good abstraction in sequential programming models because all kinds of objects can be implemented using variables. Things are more complicated for distributed computing because of race conditions: complex concurrent editing can often lead to inconsistent states. Crit- ical sections offer a generic solution to this problem but at a high cost: they reduce parallelism and they are unable to tolerate faulty behaviors. A better solution is to design the shared objects directly, without using shared memory.This deliverable surveys the main consistency criteria that exist in the literature, and expresses them in a consistent way, thereby making it easy to compare them. An object should be totally specified by two facets: a sequential specification given by an abstract data type, and a consis- tency criterion, that defines a link between distributed histories and sequential specifications. Sequential specifications are very easy to design because they are based on the well studied and understood notions of languages and automata. This makes it possible to apply all the tools de- veloped for sequential systems, from their simple definition using structures and classes to the most advanced techniques like model checking and formal verification. Sequential objects cannot be used directly in distributed environments. A consistency criterion is necessary to adapt the sequential specification to the environment. Graphically, we can imagine a consistency criterion as a way to take a picture of the distributed histories so that they look sequential.The remainder of this document is organized as follows. Section 2 presents the basic notions of sequential specification and consistency criteria and studies their general properties. Section 3 surveys the main consistency criteria existing in the literature. Section 4 provides a brief descriptions of recent systems that trade off some consistency for performance. Finally, Section 5 concludes the survey