What is it about?

A common data type for collaborative editing is RGA (Replicated Growable Array). When used for editing, RGA has two drawbacks; finding a specific element requires an expensive linear search; and each character in the text (including deleted character) is decorated with metadata. The techniques proposed in this paper substantially decrease this overhead: (i) We add an auxiliary hash table in front of RGA to locate elements quickly; (ii) many consecutive characters are buffered into a single element (hence a single piece of metadata), which however remains "splittable" to the granularity of a single character when required.

Featured Image

Why is it important?

Sequence CRDTs in general, and RGA in particular, are widely used in collaborative editing software. The techniques in this paper dramatically improve bandwidth usage and merge time, without affecting response time or latency.

Perspectives

The same techniques can be applied to other edit CRDTs.

Marc Shapiro

Read the Original

This page is a summary of: High Responsiveness for Group Editing CRDTs, November 2016, ACM (Association for Computing Machinery),
DOI: 10.1145/2957276.2957300.
You can read the full text:

Read

Contributors

The following have contributed to this page