D.1.2 – Modular quasi-causal data structures

Davide Frey (1) , Roy Friedman (2) , Achour Mostefaoui (3) , Matthieu Perrin (3, 4) , Michel Raynal (5) , François Taïani (1, 6)

1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
2 Technion - Israel Institute of Technology [Haifa]
3 GDD - Gestion de Données Distribuées [Nantes]
4 AELOS
5 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires
6 UR - Université de Rennes

In large scale systems such as the Internet, replicating data is an essential feature in order to provide availability and fault-tolerance. Attiya and Welch proved that using strong consistency criteria such as atomicity is costly as each operation may need an execution time linear with the latency of the communication network. Weaker consistency criteria like causal consistency and PRAM consistency do not ensure convergence. The different replicas are not guaranteed to converge towards a unique state. Eventual consistency guarantees that all replicas eventually converge when the participants stop updating. However, it fails to fully specify the semantics of the operations on shared objects and requires additional non-intuitive and error-prone distributed specification techniques. In addition existing consistency conditions are usually defined independently from the computing entities (nodes) that manipulate the replicated data; i.e., they do not take into account how computing entities might be linked to one another, or geographically distributed. In this deliverable, we address these issues with two novel contributions. The first contribution proposes a notion of proximity graph between computing nodes. If two nodes are connected in this graph, their operations must satisfy a strong consistency condition, while the operations invoked by other nodes are allowed to satisfy a weaker condition. We use this graph to provide a generic approach to the hybridization of data consistency conditions into the same system. Based on this, we design a distributed algorithm based on this proximity graph, which combines sequential consistency and causal consistency (the resulting condition is called fisheye consistency). The second contribution of this deliverable focuses on improving the limitations of eventual consistency. To this end, we formalize a new consistency criterion, called update consistency, that requires the state of a replicated object to be consistent with a linearization of all the updates. In other words, whereas atomicity imposes a linearization of all of the operations, this criterion imposes this only on updates. Consequently some read operations may return outdated values. Update consistency is stronger than eventual consistency , so we can replace eventually consistent objects with update consistent ones in any program. Finally, we prove that update consistency is universal, in the sense that any object can be implemented under this criterion in a distributed system where any number of nodes may crash.

Mots clés: Eventual Consistency; Sequential Consistency; Causal consistency; Scalability; Distributed Computer Systems

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Théorie de l'information [cs.IT]

Davide Frey, Roy Friedman, Achour Mostefaoui, Matthieu Perrin, Michel Raynal, et al.. D.1.2 – Modular quasi-causal data structures. [Research Report] D1.2, LINA-University of Nantes; IRISA. 2015. ⟨hal-01223119⟩