Multi-core accelerated CRDT for large-scale and dynamic collaboration

With the advancement of networking technologies and large-scale social computing, multi-user collaboration is becoming popular. In large-scale and dynamic collaborative environments, users may arbitrarily join or quit a collaboration group and work on common tasks for a long time. When users synchronize their work with the other collaborators, a large number of concurrent updates from the collaborators must be reconciled or merged to produce a consistent document state, which could challenge existing consistency maintenance approaches. Our idea is to accelerate the commutative replicated data type (CRDT)-based consistency maintenance algorithms with multi-core processors. We theoretically prove a general commutative condition for CRDT operations. One typical CRDT algorithm, replicated growable array (RGA), is transformed into Parallel RGA (PRGA) under the guidance of the general commutative condition. PRGA allows a batch of RGA operations to be executed in parallel. Experimental results showed that when processing millions of concurrent updates, PRGA achieves approximately 4x performance gains over RGA on an ordinary four-core processor.