Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1109/ICDE.2019.00022 | 2019 IEEE 35th International Conference on Data Engineering (ICDE) |
Keywords | Field | DocType |
Synchronization,Lattices,Optimization,Redundancy,Distributed databases,Conferences,Data engineering | Replica,Graph,Synchronization,Computer science,Inefficiency,Data type,Synchronization algorithm,Merge (version control),Distributed computing,Data consistency | Journal |
Volume | ISSN | Citations |
abs/1803.02750 | 1084-4627 | 0 |
PageRank | References | Authors |
0.34 | 17 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Vitor Enes | 1 | 1 | 1.37 |
Paulo Sérgio Almeida | 2 | 268 | 23.03 |
Carlos Baquero | 3 | 132 | 14.10 |
João Leitão | 4 | 159 | 16.95 |