Abstract
We address a fundamental issue of interfaces that arises in the context of cloud computing. We define what it means for a replicated and distributed implementation satisfy the standard sequential specification of the data structure. Several extant implementations of replicated data structures already satisfy the constraints of our definition. We describe how the algorithms discussed in a recent survey of convergent or commutative replicated datatypes [17] satisfy our definition. We show that our definition simplifies the programmer task significantly for a class of clients who conform to the CALM principle [10].
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
Bouajjani, A., Enea, C., Hamza, J.: Verifying eventual consistency of optimistic replication systems. In POPL 2014, pp. 285–296 (2014)
Burckhardt, S., Gotsman, A., Yang, H., Zawirski, M.: Replicated data types: specification, verification, optimality. In: POPL 2014, pp. 271–284 (2014)
Burckhardt, S., Leijen, D., Fähndrich, M., Sagiv, M.: Eventually consistent transactions. In: Seidl, H. (ed.) Programming Languages and Systems. LNCS, vol. 7211, pp. 67–86. Springer, Heidelberg (2012)
Conway, N., Marczak, W.R. et al.: Logic and lattices for distributed programming. In: ACM Symposium on Cloud Computing, pp. 1:1–1:14 (2012)
Derrick, J., Dongol, B., et al.: Quiescent consistency: defining and verifying relaxed linearizability. In: Formal, Methods, pp. 200–214 (2014)
Ellis, C.A., Gibbs, S.J.: Concurrency control in groupware systems. ACM SIGMOD Record 18(2), 399–407 (1989)
Filipovic, I., O’Hearn, P.W., Rinetzky, N., Yang, H.: Abstraction for concurrent objects. Theoretical Comp. Sci. 411, 4379–4398 (2010)
Gilbert, S., Lynch, N.: Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, pp. 51–59 (2002)
Gotsman, A., Yang, H.: Composite replicated data types. In: Vitek, J. (ed.) ESOP 2015. LNCS, vol. 9032, pp. 585–609. Springer, Heidelberg (2015)
Hellerstein, J.M.: The declarative imperative: Experiences and conjectures in distributed logic. SIGMOD Rec. 39(1), 5–19 (2010)
Herlihy, M., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM TOPLAS 12(3), 463–492 (1990)
Jagadeesan, R., Riely, J.: Between linearizability and quiescent consistency. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 220–231. Springer, Heidelberg (2014)
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978)
Panangaden, P., Shanbhogue, V., Stark, E.W.: Stability and sequentiality in dataflow networks. In: ICALP 1990, pp. 308–321 (1990)
Panangaden, P., Stark, E.W.: Computations, residuals, and the power of indeterminacy. In: ICALP 1988, pp. 439–454 (1988)
Saito, Y., Shapiro, M.: Optimistic replication. Comput. Surv. 37(1), 42–81 (2005)
Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M.: A comprehensive study of Convergent and Commutative Replicated Data Types. TR 7506, Inria (2011)
Terry, D.B., Theimer, M.M. et al.: Managing update conflicts in bayou, a weakly connected replicated storage system. In: SOSP (1995)
Vogels, W.: Eventually consistent. Communications of the ACM 52(1), 40–44 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jagadeesan, R., Riely, J. (2015). From Sequential Specifications to Eventual Consistency. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9135. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47666-6_20
Download citation
DOI: https://doi.org/10.1007/978-3-662-47666-6_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47665-9
Online ISBN: 978-3-662-47666-6
eBook Packages: Computer ScienceComputer Science (R0)