Real‑Time Collaboration Algorithms – CRDT & OT in a Task Board

How do you build a collaborative Kanban board where multiple users can drag, edit, and reorder tasks simultaneously without conflicts? This deep dive explores the theory of Operational Transformation (OT) and Conflict‑Free Replicated Data Types (CRDT), and how they shaped the design of a real‑time task board with offline support and optimistic UI.

The Problem: Concurrent Edits in a Shared Space

Imagine two users working on the same task board. User A moves a task from “To Do” to “In Progress” while User B edits its title. In a naive system, one update could overwrite the other, leading to lost work. The goal of collaboration algorithms is eventual consistency: every client’s view converges to the same state, even if updates happen offline or concurrently.

There are two dominant approaches: Operational Transformation (OT) and Conflict‑Free Replicated Data Types (CRDT). I’ll explain both, then show how our task board implements a pragmatic hybrid.

1. Operational Transformation (OT)

OT breaks every user action into atomic operations (e.g., insert character, delete character, move task). Each operation carries a baseline reference – the state it was applied to. When two operations happen concurrently, they are transformed against each other so that applying them in any order yields the same final state.

// Simplified OT example (text editing)
// Client A inserts 'x' at position 5
opA = { type: 'insert', pos: 5, char: 'x', base: versionA }

// Client B deletes at position 3
opB = { type: 'delete', pos: 3, length: 1, base: versionB }

// Server transforms opA against opB and vice versa
transformedOpA = transform(opA, opB) // pos may shift due to deletion
transformedOpB = transform(opB, opA) // similarly adjusted

OT is widely used in Google Docs and collaborative editors. Its strength is fine‑grained control, but the transformation logic becomes extremely complex for nested structures like JSON (the “TP2” puzzle). Our task board’s data (tasks with positions, columns, titles) is simpler, so OT is feasible, but we opted for a CRDT‑inspired approach for offline robustness.

2. Conflict‑Free Replicated Data Types (CRDT)

CRDTs achieve eventual consistency by design: each piece of data is so small that concurrent updates commute. For text, a CRDT treats every character as an independent entity with a unique ID. When two users insert characters, the CRDT ensures they appear in the right order without transformation – the only thing that needs adjusting is the position.

// CRDT text representation (simplified)
let doc = {
  'char_abc123': { value: 'H', pos: [1, 'char_abc122'], ... },
  'char_def456': { value: 'i', pos: [2, 'char_abc123'], ... }
}

For our task board, we applied CRDT thinking to task ordering. Instead of using integer ranks (which cause conflicts), we used fractional indexing (like the LSEQ tree). Each task gets a position identifier that can be split infinitely, so concurrent inserts generate unique, ordered positions without coordination.

System Architecture

Conflict Resolution Strategies

We treat the server as the source of truth. Operations are processed in arrival order, but we defined clear rules for concurrent scenarios:

Example of move conflict resolution:

// Server-side handler for move event
socket.on('task:move', async (data) => {
  const { taskId, newColumn, newRank, clientVersion } = data;
  // Check current task in DB
  const current = await db.task.findUnique(taskId);
  if (current.version > clientVersion) {
    // Conflict – broadcast current state and notify loser
    io.emit('task:update', current);
    socket.emit('conflict:lost', { taskId, currentState: current });
  } else {
    // Apply move
    const updated = await db.task.update(...);
    io.emit('task:update', updated);
  }
});

Offline Support & Optimistic UI

The frontend monitors Socket.IO connection status. When disconnected, all user actions are still applied optimistically to the Zustand store, giving instant feedback. Instead of being sent immediately, they are pushed into an in‑memory queue.

// offlineQueue.ts
class OfflineQueue {
  queue = [];
  isConnected = true;

  add(action) {
    this.queue.push(action);
    if (this.isConnected) this.flush();
  }

  async flush() {
    while (this.queue.length) {
      const action = this.queue.shift();
      try {
        await socket.emit(action.type, action.payload);
      } catch (err) {
        // Re-queue on failure
        this.queue.unshift(action);
        break;
      }
    }
  }
}

Tasks created offline get a temporary ID (e.g., temp‑123). They are disabled for editing until the server confirms creation and replaces the ID. On reconnection, the queue is flushed in order, and the client reconciles any differences via server broadcasts.

Under the Hood: Fractional Indexing for Order

Traditional integer ranks lead to conflicts when two clients insert between the same ranks. We used a fractional indexing scheme (similar to LSEQ) that generates a string sort key between two existing keys without requiring coordination.

// Generate a key between a and b (a < b)
function generateKeyBetween(a, b) {
  if (a === null) return b ? b.padStart(b.length, '0') : 'a0';
  if (b === null) return a + 'z';
  // Average lexicographically
  let i = 0;
  while (i < a.length && i < b.length && a[i] === b[i]) i++;
  let diff = b.charCodeAt(i) - a.charCodeAt(i);
  if (diff > 1) {
    return a.slice(0, i) + String.fromCharCode(a.charCodeAt(i) + 1);
  } else {
    return a.slice(0, i+1) + generateKeyBetween(a.slice(i+1), '');
  }
}

This is a lightweight CRDT for ordering – no central coordination needed, and concurrent inserts always produce consistent ordering.

Features Implemented

• Three‑column Kanban (To Do, In Progress, Done) with drag‑and‑drop using dnd‑kit.
• Real‑time sync <200ms latency via Socket.IO.
• Optimistic UI – all changes appear instantly, then reconciled.
• Offline queue – actions are stored and replayed on reconnect.
• Conflict resolution as described above, with toast notifications for losing moves.
• Multi‑user presence – avatars showing who is viewing/editing each task.
• Persistent storage with PostgreSQL and Prisma ORM.

Tech Stack

Lessons Learned

Further Reading

• Operational Transformation – Wikipedia
• CRDT.tech – Overview & papers
• How Figma’s Multiplayer Technology Works
• A CRDT for JSON (Martin Kleppmann)