Cited By
View all- Jannes KLagaisse BJoosen W(2021)OWebSync: Seamless Synchronization of Distributed Web ClientsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.306627632:9(2338-2351)Online publication date: 1-Sep-2021
Dynamic adaptation of geo-replicated CRDTs
Pages 514 - 521
Abstract
Conflict-free Replicated Data Types (CRDTs) are high-level data types that can be replicated with minimal coordination among replicas due to its confluent semantics. This property makes CRDTs specially appealing for geo-replicated settings. Different approaches, such as state transfer and operation forwarding, have been proposed to propagate updates among replicas, with different tradeoffs among the amount of network traffic generated and the staleness of local information. This paper proposes and evaluates techniques to automatically adapt a CRDT implementation, such that the best approach is used, based on the application needs (captured by a SLA) and the observed system configuration. Our techniques have been integrated in SwiftCloud, a state of the art geo-replicated store based on CRDTs.
References
[1]
P. Almeida, A. Shoker, and C. Baquero. Efficient state-based CRDTs by delta-mutation. CoRR, abs/1410.2803, 2014.
[2]
C. Baquero, P. Almeida, and A. Shoker. Making operation-based CRDTs operation-based. In K. Magoutis and P. Pietzuch, editors, Distributed Applications and Interoperable Systems, LNCS, pages 126--140. Springer Berlin Heidelberg, 2014.
[3]
A. Bieniusa, M. Zawirski, N. Preguiça, M. Shapiro, C. Baquero, V. Balegas, and S. Duarte. An optimized conflict-free replicated set. CoRR, abs/1210.3368, 2012.
[4]
B. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with YCSB. In SoCC, 2010.
[5]
M. Couceiro, G. Chandrasekara, M. Bravo, M. Hiltunen, P. Romano, and L. Rodrigues. Q-opt: Self-tuning quorum system for strongly consistent software defined storage. In Middleware '15, Vancouver, BC, Canada, 2015.
[6]
V. Hodge and J. Austin. A survey of outlier detection methodologies. Artificial Intelligence Review, 22(2):85--126, 2004.
[7]
R. Kalman. A new approach to linear filtering and prediction problems. Journal of Fluids Engineering, 82(1):35--45, 1960.
[8]
L. Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133--169, May 1998.
[9]
M. Letia, N. Preguiça, and M. Shapiro. CRDTs: Consistency without concurrency control. CoRR, abs/0907.0929, 2009.
[10]
W. Lloyd, M. Freedman, M. Kaminsky, and D. Andersen. Don't settle for eventual: Scalable causal consistency for wide-area storage with COPS. In SOSP, 2011.
[11]
A. Metwally, D. Agrawal, and A. El Abbadi. Efficient computation of frequent and top-k elements in data streams. In ICDT, volume 3363 of LNCS, pages 398--412. Springer, 2005.
[12]
D. Navalho, S. Duarte, N. Preguiça, and M. Shapiro. Incremental stream processing using computational conflict-free replicated data types. CloudDP, 2013.
[13]
E. Page. Continuous inspection schemes. Biometrika, 41(1/2):pp. 100--115, 1954.
[14]
N. Preguiça, J. Marques, M. Shapiro, and M. Letia. A commutative replicated data type for cooperative editing. In ICDCS, 2009.
[15]
M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. A comprehensive study of Convergent and Commutative Replicated Data Types. Research Report RR-7506, 2011.
[16]
M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. Conflict-free replicated data types. SSS, 2011.
[17]
D. Terry, A. Demers, K. Petersen, M. Spreitzer, M. Theimer, and B. Welch. Session guarantees for weakly consistent replicated data. In PDIS, 1994.
[18]
D. Terry, V. Prabhakaran, R. Kotla, M. Balakrishnan, M. Aguilera, and H. Abu-Libdeh. Consistency-based service level agreements for cloud storage. SOSP, 2013.
[19]
W. Vogels. Eventually consistent. Commun. ACM, 52(1):40--44, Jan. 2009.
[20]
M. Zawirski, N. Preguiça, S. Duarte, A. Bieniusa, V. Balegas, and M. Shapiro. Write fast, read in the past: Causal consistency for client-side applications. Middleware, 2015.
Recommendations
Making CRDTs Byzantine fault tolerant
PaPoC '22: Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed DataIt is often claimed that Conflict-free Replicated Data Types (CRDTs) ensure consistency of replicated data in peer-to-peer systems. However, peer-to-peer systems usually consist of untrusted nodes that may deviate from the specified protocol (i.e. ...
Improving the Reactivity of Pure Operation-Based CRDTs
PaPoC '21: Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed DataModern distributed applications increasingly replicate data to guarantee both high availability of the system and an optimal user experience. Conflict-Free Replicated Data Types (CRDTs) are a family of data types specially designed for highly available ...
Memory efficient CRDTs in dynamic environments
VMIL 2019: Proceedings of the 11th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate LanguagesModern distributed applications increasingly replicate data in order to guarantee both high availability of systems and an optimal user experience. Conflict-Free Replicated Data Types (CRDTs) are a family of data types specially designed for highly ...
Comments
Information & Contributors
Information
Published In
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 April 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
SAC 2016
Sponsor:
Acceptance Rates
SAC '16 Paper Acceptance Rate 252 of 1,047 submissions, 24%;
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 92Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)0
Reflects downloads up to 06 Nov 2024
Other Metrics
Citations
Cited By
View all- Jannes KLagaisse BJoosen W(2021)OWebSync: Seamless Synchronization of Distributed Web ClientsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.306627632:9(2338-2351)Online publication date: 1-Sep-2021
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in