Paulo Sérgio Almeida

"Efficient Synchronization of State-based Conflict-Free Replicated Datatypes"

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.

Bio: Paulo Sérgio Almeida is an Assistant Professor at University of Minho, and a senior researcher atHASLab / INESC TEC. He obtained a MSc degree from University of Porto in 1994and a PhD degree in Computer Science from Imperial College London in 1998.His research activities have been in the area of distributed systems. Some maincontributions have been in causality tracking mechanisms, eventuallyconsistent databases, and fault-tolerant distributed aggregationalgorithms. Other subjects have been bloom filters and distributed algorithmsin graphs. For some years the main focus of research has been on CRDTs(Conflict-free Replicated Data Types), with some results being the developmentof both pure operation-based and delta-state based CRDTs.