# CRDT Design Documentation

This directory contains the design documentation for Notive's collaborative music notation CRDT implementation.

## Documents

### [crdt-design.md](./crdt-design.md)
The foundational design document covering:
- Why we need a custom operation-based CRDT (not Automerge/Yjs)
- Core type definitions (Cell, Grid, Operations)
- Domain constraints (duration preservation, subdivisions)
- Initial conflict resolution options
- Related to existing TypeScript implementation

### [fractional-indexing.md](./fractional-indexing.md)
Deep dive into stable position identifiers:
- Why array indices don't work for concurrent edits
- How fractional indexing provides stable cell references
- Implementation details and examples
- Handling position space exhaustion
- Production considerations

### [branch-based-merge.md](./branch-based-merge.md)
Advanced conflict detection and resolution strategy:
- Detecting concurrent operations with vector clocks
- Grouping operations into causal branches
- Reconstructing per-actor views of state
- Smart conflict detection (overlapping subdivisions, lost edits, duration mismatches)
- User experience for merge conflicts
- Automatic resolution where safe, user control where ambiguous

## Reading Order

For someone new to the project:
1. Start with **crdt-design.md** for context and requirements
2. Read **fractional-indexing.md** to understand cell positioning
3. Review **branch-based-merge.md** for the conflict resolution strategy

## Implementation Status

The CRDT is being implemented as a Rust crate in `/crdt`:
- ✅ Vector clock implementation
- ✅ Basic Doc structure with operation log
- ✅ Core domain types (Cell, Row, Grid, DerivedId)
- ✅ CreateGrid operation
- ✅ ChangeSubdivisions operation
- ❌ Fractional indexing (decided not to use in operations)
- ⏳ Conflict detection
- ⏳ Branch-based merge

## Design Principles

1. **Causal Consistency** - Operations respect causality via vector clocks
2. **Deterministic Realization** - Each branch produces consistent state from its operation sequence
3. **No Silent Data Loss** - Conflicts are explicit, not silently resolved
4. **Domain Invariants** - Preserve musical constraints (e.g., row duration)
5. **User Control** - Explicit conflict resolution for ambiguous concurrent edits
6. **Simplicity Over Commutativity** - Branch-based resolution instead of forcing all operations to commute

## Key Architectural Decisions

- **Operation-based CRDT** (not state-based) for semantic operations
- **Vector clocks** for causality tracking (future: consider Hybrid Logical Clocks)
- **Deterministic IDs** using `DerivedId` (no fractional indexing in operations)
- **Range-based subdivision** instead of tombstones (simpler semantics)
- **Branch-based conflict resolution** rather than automatic commutativity
- **User-driven resolution** for ambiguous concurrent edits

## Future Work

- Hybrid Logical Clocks for wall-clock ordering
- Snapshot and compaction strategy
- Server-side operation validation
- Operational transformation for some conflicts
- Multi-grid support and cross-grid operations
- Undo/redo with CRDT semantics