Evaluation of sequence based CRDTs

Job description

Contexte et atouts du poste

This master internship will be in the context of Alvearium challenge ( a project between Hivenet, Loreley, Magellan, Pesto and Wide Inria teams.

The engineer will be located at Inria Nancy-Grand Est in Loreley team.

Hivenet intends to play the role of a next generation cloud provider in the context of Web 3.0. Hivenet aims to exploit the unused capacity of computers to offer the general public a greener and more sovereign alternative to the existing clouds where the true power lies in the hands of the users.

It relies both on distributed peer-to-peer networks and on the end-to-end encryption of data.

Mission confiée

Replication mechanisms can be classified into optimistic and pessimistic.

Pessimistic replication approaches block access to a replica unless it is provably up-to-date.

Optimistic approaches let data be read or written without synchronisation, based on the assumption that conflicts caused by concurrent changes occur only rarely [1].

In this case replicas are allowed to diverge and they will converge later after the reception of all updates.

Two main optimistic replication approaches exist for maintaining consistency over shared data: operational transformation (OT) and commutative replicated data types (CRDT).

The OT approach [2] relies on two components: a set of transformation functions specific to a document type that specify how concurrent modifications are merged and a generic integration algorithm that detects concurrent
changes and applies the appropriate transformation functions.

This mechanism is currently integrated in GoogleDocs.

This approach has several limitations.

It does not scale with the number of users and requires either a central server for message dissemination or expensive distributed consensus protocols.

Moreover, the algorithmic complexity is quadratic in the number of concurrent operations.

Furthermore, it requires the detection of concurrency between operations.

It has been shown that the size of the optimal data structure for concurrency detection is proportional to the number of collaborators.

This structure is very costly in terms of storage and communication as it must be attached to every modification.

Finally, the design of correct transformation functions is complex and costly.

In order to address the limitations of OT, CRDTs [3,4] were proposed.

The main idea is to define data structures where parallel modifications are conflict free.

This approach has several advantages.

It does not require a posteriori synchronisation as concurrent modifications are executed without conflict and produce the same state on all copies independently of the execution order.

The architecture can be therefore completely distributed.

The algorithmic complexity is much lower than that of the OT mechanism.

Our previous study in [5] compared optimistic replication approaches including OT approaches and the first CRDTs existing at that time.

This master thesis will focus on sequence-based CRDTs such as [6,7] in the context of collaborative editing.

We will analyze the complexity of these algorithms from a theoretical point of view, but also from a practical point of view with the help of real collaboration traces.

We will build a common benchmark for measuring different performance metrics.

Bibliography:

1.

Y.

Saito and M.

Shapiro.

2005.

Optimistic replication.

Computing Surveys, 37: 1, (Mar.

2005) pp.

42–81.

3.

G.

Oster, P.

Urso, P.

Molli, and A.

Imine.

2006.

Data consistency for p2p collaborative editing.

In Proceedings of the ACM Conference on Computer-Supported Cooperative Work(CSCW2006).

Association for Computing Machinery, Banff, AB, Canada, (Nov.

2006) pp.

259–267.

4.

M.

Shapiro, N.

Preguiça, C.

Baquero, and M.

Zawirski.

2011.

Conflict-free replicated data types.

In Proceedings of the International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2011).

Springer, Grenoble, France, (Oct.

2011) pp.

386–400.

5.

M.

Ahmed-Nacer, C.-L.

Ignat, G.

Oster, H.-G.

Roh, and P.

Urso.

2011.

Evaluating CRDTs for real-time document editing.

In Proceedings of the 2011 ACM Symposium on Document Engineering (DocEng 2011).

Association for Computing Machinery, Mountain View, CA, USA, (Sept.

2011) pp.

103–112.

6.

L.

André, S.

Martin, G.

Oster, and C.-L.

Ignat.

2013.

Supporting adaptable granularity of changes for massive-scale collaborative editing.

In Proceedings of the IEEE International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom 2013).

IEEE Computer Society, Austin, Texas, USA, (Oct.

2013) pp.
50–59.

7.

Joseph Gentle and Martin Kleppmann.

Collaborative Text Editing with Eg-walker: Better, Faster, Smaller.

20th European Conference on Computer Systems (EuroSys), April 2025.

Principales activités

- Study the literature on CRDTs and sequence-based CRDTs (1 month)
- Implement a benchmark allowing the comparison of the various CRDT-based algorithms (1 months)
- Implement existing sequence-based CRDTs on the proposed benchmark (1 months)
- Compare the sequence-based CRDTs and evaluate them using the banchmark and simulated traces (2 months)
- Write the master thesis report (2 weeks)

Compétences

Enrolled in a Master 2 in Computer science / Applied mathematics with an experience in computer networks.

Theoretical expertise: distributed systems, P2P networks

Good collaborative and networking skills, excellent written and oral communication in English

Good programming skills

Strong analytical skills

Avantages

Required Skill Profession

Computer Occupations