2018/03/07 by Vitor Enes, Paulo Sérgio Almeida, Enes, Vitor +5 · 2 voices · 1 citation
#cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1803.02750
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 synchronisation 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) evaluate the improved algorithms.