Building a Basic CRDT Framework in JavaScript

Conflict-free Replicated Data Types (CRDTs) are a powerful tool for building distributed systems where data needs to be replicated across multiple nodes without requiring explicit coordination or locking. This challenge asks you to implement a simplified CRDT framework in JavaScript, focusing on a core operation: building a counter CRDT. This will give you a foundational understanding of CRDT principles and their implementation.

Problem Description

You are tasked with creating a JavaScript framework capable of representing and synchronizing a simple counter CRDT. The counter CRDT should allow for increment and decrement operations. The framework should ensure that, regardless of the order in which these operations are applied across different replicas, all replicas eventually converge to the same final counter value.

What needs to be achieved:

1. Counter CRDT Class: Create a class named CounterCRDT that encapsulates the counter's state and operations.
2. Increment Operation: Implement an increment() method that increases the counter's value. This method should return a unique operation ID (a simple string will suffice, e.g., a timestamp).
3. Decrement Operation: Implement a decrement() method that decreases the counter's value. This method should also return a unique operation ID.
4. Apply Operation: Implement an applyOperation(operationId, amount) method. This method takes an operation ID and the amount (positive for increment, negative for decrement) and applies the corresponding change to the counter's state.
5. GetValue: Implement a getValue() method that returns the current value of the counter.

Key Requirements:

• Convergence: The core principle is that applying operations in any order across multiple CounterCRDT instances should eventually lead to all instances having the same value.
• Operation IDs: Each increment and decrement operation must be associated with a unique ID. This is crucial for ensuring convergence.
• Idempotency: Applying the same operation (same operation ID) multiple times should have the same effect as applying it once.

Expected Behavior:

• Multiple instances of CounterCRDT should be able to operate independently.
• Operations applied to one instance should be able to be applied to other instances, and the instances should converge to the same value.
• The getValue() method should always return the current, consistent value of the counter.

Edge Cases to Consider:

• What happens if an operation is applied out of order? The CRDT should still converge.
• What happens if an operation is applied multiple times? It should be idempotent.
• Consider how to handle potential overflow/underflow scenarios (though a simple integer counter is sufficient for this challenge).

Examples

Example 1:

// Replica 1
const counter1 = new CounterCRDT();
const op1 = counter1.increment();
const op2 = counter1.increment();
console.log("Counter 1 Value:", counter1.getValue()); // Output: 2

// Replica 2
const counter2 = new CounterCRDT();
counter2.applyOperation(op1, 1);
counter2.applyOperation(op2, 1);
console.log("Counter 2 Value:", counter2.getValue()); // Output: 2

Explanation: Both replicas start with a value of 0. Replica 1 increments twice, resulting in a value of 2. Replica 2 then applies the same operations, also resulting in a value of 2.

Example 2:

// Replica 1
const counter1 = new CounterCRDT();
const op1 = counter1.increment();
console.log("Counter 1 Value:", counter1.getValue()); // Output: 1

// Replica 2
const counter2 = new CounterCRDT();
counter2.applyOperation(op1, 1);
console.log("Counter 2 Value:", counter2.getValue()); // Output: 1

// Replica 1 applies a decrement after Replica 2 has already applied the increment
counter1.decrement();
console.log("Counter 1 Value:", counter1.getValue()); // Output: 0
console.log("Counter 2 Value:", counter2.getValue()); // Output: 0

Explanation: Replica 1 increments, Replica 2 applies the increment. Replica 1 then decrements. Both replicas converge to 0.

Example 3: (Out of Order Application)

const counter1 = new CounterCRDT();
const op1 = counter1.increment();
const op2 = counter1.increment();

const counter2 = new CounterCRDT();
counter2.applyOperation(op2, 1); // Apply op2 before op1
counter2.applyOperation(op1, 1); // Now apply op1
console.log("Counter 2 Value:", counter2.getValue()); // Output: 2

Explanation: Demonstrates that applying operations out of order still leads to convergence.

Constraints

• Operation ID Length: Operation IDs should be at least 10 characters long to minimize collision probability. A simple timestamp-based ID is acceptable.
• Counter Value Type: The counter value should be a JavaScript number.
• Performance: While not a primary focus, the operations should be reasonably efficient. Avoid unnecessary complexity.
• No External Libraries: You should not use any external libraries for this challenge. The goal is to understand the core CRDT concepts.

Notes

• This is a simplified CRDT implementation. Real-world CRDTs can be significantly more complex.
• Focus on the core principles of convergence and idempotency.
• Consider how you might generate unique operation IDs. A simple timestamp combined with a random number can work.
• Think about how the applyOperation method ensures that operations are applied correctly, regardless of their order.
• The key to CRDTs is that they are commutative. The order of operations doesn't matter.