A Constraint-based Formalism for Consistency in Replicated Systems

Abstract : We present a formalism for modeling replication in a distributed system with concurrent users sharing information. It is based on actions, which represent operations requested by independent users, and constraints, representing scheduling relations between actions. The formalism encompasses semantics of shared data, such as commutativity or conflict between actions, and user intents such as causal dependence or atomicity. It enables us to reason about the consistency properties of a replication protocol or of classes of protocols. It supports weak consistency (optimistic protocols) as well as the stronger pessimistic protocols. Our approach clarifies the requirements and assumptions common to all replication systems. We are able to prove a number of common properties. For instance consistency properties that appear different operationally are proved equivalent under suitable liveness assumptions. The formalism enables us to design a new, generalised peer-to-peer consistency protocol.
keyword : syn optim rep
Type de document :
Communication dans un congrès
OPODIS 2004 - 8th International Conference on Principles of Distributed Systems, Dec 2004, Grenoble, France. 3544, pp.331--345, 2004, Lecture Notes in Computer Science. 〈10.1007/11516798_24〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00444799
Contributeur : Marc Shapiro <>
Soumis le : jeudi 7 janvier 2010 - 11:43:51
Dernière modification le : dimanche 9 décembre 2018 - 01:20:09
Document(s) archivé(s) le : jeudi 17 juin 2010 - 20:34:18

Fichier

opodis2004-final-2004-10-30.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Marc Shapiro, Karthikeyan Bhargavan, Nishith Krishna. A Constraint-based Formalism for Consistency in Replicated Systems. OPODIS 2004 - 8th International Conference on Principles of Distributed Systems, Dec 2004, Grenoble, France. 3544, pp.331--345, 2004, Lecture Notes in Computer Science. 〈10.1007/11516798_24〉. 〈inria-00444799〉

Partager

Métriques

Consultations de la notice

355

Téléchargements de fichiers

171