Conflict-Free Replicated Data Type (CRDT) Implementation in JavaScript

Conflict-free replicated data types (CRDTs) are essential for building distributed systems where data needs to be synchronized across multiple nodes without requiring strict coordination. This challenge asks you to implement a simple CRDT – a Grow-Only Counter – in JavaScript. Successfully implementing this will demonstrate your understanding of CRDT principles and their application in distributed data management.

Problem Description

You are tasked with creating a JavaScript class representing a Grow-Only Counter CRDT. This CRDT allows incrementing a counter value but never decrementing it. Multiple replicas of this counter can exist across different nodes, and updates (increments) can be applied concurrently. The CRDT guarantees that all replicas will eventually converge to the same final value, regardless of the order in which updates are applied.

Key Requirements:

• Increment Operation: The CRDT must provide a method to increment the counter. This method should return a unique identifier (UUID) for the increment operation.
• Merge Operation: The CRDT must provide a method to merge with another CRDT instance. This operation should incorporate all increments from the other CRDT into the current CRDT, ensuring convergence.
• Value Retrieval: The CRDT must provide a method to retrieve the current value of the counter.
• Unique Increment IDs: Each increment operation must generate a unique identifier (UUID). This is crucial for conflict resolution during merging.

Expected Behavior:

• Incrementing the counter multiple times on the same replica should increase the value accordingly.
• Merging two replicas with different increment histories should result in a merged replica with the combined increment history.
• Merging a replica with itself should have no effect (other than potentially re-ordering increments internally).
• The final counter value should always be non-negative.

Edge Cases to Consider:

• Merging with an empty CRDT (one that has never been incremented).
• Merging a CRDT with itself multiple times.
• Handling potential issues with UUID generation (though for this exercise, you can assume UUID generation is reliable).

Examples

Example 1:

Input:
CRDT instance 'counter1'
counter1.increment(); // Returns UUID "a1b2c3d4-e5f6-7890-1234-567890abcdef"
counter1.increment(); // Returns UUID "fedcba98-7654-3210-fedc-ba9876543210"
counter1.value(); // Returns 2

CRDT instance 'counter2'
counter2.increment(); // Returns UUID "11223344-5566-7788-9900-aabbccddeeff"
counter2.increment(); // Returns UUID "00ffeedd-ccbbaa-9988-7766-554433221100"
counter2.value(); // Returns 2

counter1.merge(counter2);
counter1.value(); // Returns 4

Explanation: counter1 has two increments, and counter2 has two increments. Merging them combines the increments, resulting in a final value of 4.

Example 2:

Input:
CRDT instance 'counter1'
counter1.increment(); // Returns UUID "123e4567-e89b-12d3-a456-426614174000"
counter1.increment(); // Returns UUID "987f6543-210e-f3d2-c4b5-a67890123456"
counter1.value(); // Returns 2

CRDT instance 'counter2' (empty)
counter2.value(); // Returns 0

counter1.merge(counter2);
counter1.value(); // Returns 2

Explanation: Merging with an empty counter has no effect on the value of counter1.

Example 3: (Edge Case)

Input:
CRDT instance 'counter1'
counter1.increment(); // Returns UUID "abc12345-def6-7890-abcd-ef1234567890"
counter1.merge(counter1);
counter1.value(); // Returns 1

Explanation: Merging a CRDT with itself should not change the value.

Constraints

• UUID Generation: You can use a standard UUID generation library (e.g., uuid) or implement a simple UUID generator. Assume the UUIDs generated are globally unique.
• Data Structure: You are free to choose the data structure to store the increment history (e.g., an array, a set). The choice of data structure can impact performance, but correctness is the primary concern.
• Performance: While performance is not the primary focus, avoid excessively inefficient data structures or algorithms. The solution should be reasonably performant for a small number of increments (e.g., up to 1000).
• Input: The merge operation will only receive another instance of the Grow-Only Counter CRDT.

Notes

• The core of a Grow-Only Counter CRDT lies in its ability to merge increment histories without conflicts. The UUIDs serve as timestamps, allowing you to determine the order of increments during merging.
• Consider how you will represent the increment history internally. A sorted list of UUIDs paired with increment values (always 1) is a common approach.
• The merge operation should iterate through the increment histories of both CRDT instances and combine them in a way that preserves the order of increments based on their UUIDs.
• Focus on correctness first. Performance optimizations can be considered later if time permits.
• Remember that this is a Grow-Only counter. There should be no decrement operations.