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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Saito, Y., Shapiro, M.: Optimistic replication. Computing Surveys (2005)
Shapiro, M., Bhargavan, K.: The Actions-Constraints approach to replication: Definitions and proofs. Technical Report MSR-TR-2004-14, Microsoft Research (2004)
Sun, C., Jia, X., Zhang, Y., Yang, Y., Chen, D.: Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems. Trans. on Comp.-Human Interaction 5, 63–108 (1998)
Preguiça, N., Shapiro, M., Matheson, C.: Semantics-based reconciliation for collaborative and mobile environments. In: Meersman, R., Tari, Z., Schmidt, D.C. (eds.) CoopIS 2003, DOA 2003, and ODBASE 2003. LNCS, vol. 2888, pp. 38–55. Springer, Heidelberg (2003)
Shapiro, M., Preguiça, N., O’Brien, J.: Rufis: mobile data sharing using a generic constraint-oriented reconciler. In: Conf. on Mobile Data Management, Berkeley, CA, USA (2004)
Birell, A.D., Levin, R., Needham, R.M., Schroeder, M.D.: Grapevine: An exercise in distributed computing. Communications of the ACM 25, 260–274 (1982)
Terry, D.B., Theimer, M.M., Petersen, K., Demers, A.J., Spreitzer, M.J., Hauser, C.H.: Managing update conflicts in Bayou, a weakly connected replicated storage system. In: Proc. 15th ACM Symposium on Operating Systems Principles, Copper Mountain CO (USA). ACM SIGOPS, New York (1995)
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21, 558–565 (1978)
Fekete, A., Gupta, D., Luchangco, V., Lynch, N., Shvartsman, A.: Eventually-serializable data services. Theoretical Computer Science 220, 113–156 (1999)
Manivannan, D., Singhal, M.: An efficient distributed algorithm for detection of knots and cycles in a distributed graph. IEEE Transactions on Parallel and Distributed Systems 14, 961–972 (2003)
Chong, Y., Hamadi, Y.: Distributed IceCube. Private communication (2004)
Ramamritham, K., Chrysanthis, P.K.: A taxonomy of correctness criteria in database applications. VLDB Journal 5, 85–97 (1996)
Sousa, A., Oliveira, R., Moura, F., Pedone, F.: Partial replication in the database state machine. In: Int. Symp. on Network Comp. and App. (NCA 2001), Cambridge MA, USA, pp. 298–309. IEEE, Los Alamitos (2001)
Frølund, S., Guerraoui, R.: X-Ability: A theory of replication. In: Symp. on Principles of Dist. Comp. (PODC 2000), Portland, Oregon, USA. ACM SIGACT-SIGOPS, New York (2000)
Chrysanthis, P.K., Ramamritham, K.: ACTA: The SAGA continues. In: Elmagarmid, A.K. (ed.) Database Transaction Models for Advanced Applications, pp. 349–397. Morgan Kaufmann, San Francisco (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shapiro, M., Bhargavan, K., Krishna, N. (2005). A Constraint-Based Formalism for Consistency in Replicated Systems. In: Higashino, T. (eds) Principles of Distributed Systems. OPODIS 2004. Lecture Notes in Computer Science, vol 3544. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11516798_24
Download citation
DOI: https://doi.org/10.1007/11516798_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27324-0
Online ISBN: 978-3-540-31584-1
eBook Packages: Computer ScienceComputer Science (R0)