TY - GEN
T1 - Efficient synchronization of state-based CRDTs
AU - Enes, Vitor
AU - Almeida, Paulo Sérgio
AU - Baquero, Carlos
AU - Leitao, Joao
N1 - info:eu-repo/grantAgreement/EC/H2020/732505/EU#
info:eu-repo/grantAgreement/FCT/5876/147279/PT#
We would like to thank Ricardo Macedo, Georges Younes, Marc Shapiro and the anonymous reviewers for their valuable feedback on earlier drafts of this work. FCT - PhD Fellowship (PD/BD/142927/2018).
Carlos Baquero was partially supported by SMILES within TEC4Growth project (NORTE-01-0145-FEDER-000020).
João Leitão was partially supported by project NG-STORAGE through FCT grant PTDC/CCI-INF/32038/2017.
PY - 2019/4/1
Y1 - 2019/4/1
N2 - To ensure high availability in large scale distributed systems, Conflict-free Replicated Data Types (CRDTs) relax consistency by allowing immediate query and update operations at the local replica, with no need for remote synchronization. State-based CRDTs synchronize replicas by periodically sending their full state to other replicas, which can become extremely costly as the CRDT state grows. Delta-based CRDTs address this problem by producing small incremental states (deltas) to be used in synchronization instead of the full state. However, current synchronization algorithms for delta-based CRDTs induce redundant wasteful delta propagation, performing worse than expected, and surprisingly, no better than state-based. In this paper we: 1) identify two sources of inefficiency in current synchronization algorithms for delta-based CRDTs; 2) bring the concept of join decomposition to state-based CRDTs; 3) exploit join decompositions to obtain optimal deltas and 4) improve the efficiency of synchronization algorithms; and finally, 5) experimentally evaluate the improved algorithms.
AB - To ensure high availability in large scale distributed systems, Conflict-free Replicated Data Types (CRDTs) relax consistency by allowing immediate query and update operations at the local replica, with no need for remote synchronization. State-based CRDTs synchronize replicas by periodically sending their full state to other replicas, which can become extremely costly as the CRDT state grows. Delta-based CRDTs address this problem by producing small incremental states (deltas) to be used in synchronization instead of the full state. However, current synchronization algorithms for delta-based CRDTs induce redundant wasteful delta propagation, performing worse than expected, and surprisingly, no better than state-based. In this paper we: 1) identify two sources of inefficiency in current synchronization algorithms for delta-based CRDTs; 2) bring the concept of join decomposition to state-based CRDTs; 3) exploit join decompositions to obtain optimal deltas and 4) improve the efficiency of synchronization algorithms; and finally, 5) experimentally evaluate the improved algorithms.
KW - Crdts
KW - Join decomposition
KW - Optimal deltas
UR - http://www.scopus.com/inward/record.url?scp=85067993437&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2019.00022
DO - 10.1109/ICDE.2019.00022
M3 - Conference contribution
AN - SCOPUS:85067993437
T3 - Proceedings - International Conference on Data Engineering
SP - 148
EP - 159
BT - Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
PB - IEEE Computer Society
T2 - 35th IEEE International Conference on Data Engineering, ICDE 2019
Y2 - 8 April 2019 through 11 April 2019
ER -