Scalable and Accurate Causality Tracking for Eventually Consistent Stores

Abstract : In cloud computing environments, data storage systems often rely on optimistic replication to provide good performance and availability even in the presence of failures or network partitions. In this scenario, it is important to be able to accurately and efficiently identify updates executed concurrently. Current approaches to causality tracking in optimistic replication have problems with concurrent updates: they either (1) do not scale, as they require replicas to maintain information that grows linearly with the number of writes or unique clients; (2) lose information about causality, either by removing entries from client-id based version vectors or using server-id based version vectors, which cause false conflicts. We propose a new logical clock mechanism and a logical clock framework that together support a traditional key-value store API, while capturing causality in an accurate and scalable way, avoiding false conflicts. It maintains concise information per data replica, only linear on the number of replica servers, and allows data replicas to be compared and merged linear with the number of replica servers and versions.
Type de document :
Communication dans un congrès
David Hutchison; Takeo Kanade; Bernhard Steffen; Demetri Terzopoulos; Doug Tygar; Gerhard Weikum; Kostas Magoutis; Peter Pietzuch; Josef Kittler; Jon M. Kleinberg; Alfred Kobsa; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan. 4th International Conference on Distributed Applications and Interoperable Systems (DAIS), Jun 2014, Berlin, Germany. Springer, Lecture Notes in Computer Science, LNCS-8460, pp.67-81, 2014, Distributed Applications and Interoperable Systems. 〈10.1007/978-3-662-43352-2_6〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01287733
Contributeur : Hal Ifip <>
Soumis le : lundi 14 mars 2016 - 10:49:16
Dernière modification le : jeudi 12 mai 2016 - 10:49:53
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 17:23:02

Fichier

326177_1_En_6_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Paulo Almeida, Carlos Baquero, Ricardo Gonçalves, Nuno Preguiça, Victor Fonte. Scalable and Accurate Causality Tracking for Eventually Consistent Stores. David Hutchison; Takeo Kanade; Bernhard Steffen; Demetri Terzopoulos; Doug Tygar; Gerhard Weikum; Kostas Magoutis; Peter Pietzuch; Josef Kittler; Jon M. Kleinberg; Alfred Kobsa; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan. 4th International Conference on Distributed Applications and Interoperable Systems (DAIS), Jun 2014, Berlin, Germany. Springer, Lecture Notes in Computer Science, LNCS-8460, pp.67-81, 2014, Distributed Applications and Interoperable Systems. 〈10.1007/978-3-662-43352-2_6〉. 〈hal-01287733〉

Partager

Métriques

Consultations de la notice

32

Téléchargements de fichiers

38