# 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)
- ⏳ CreateGrid operation
- ⏳ Subdivide operation
- ⏳ Fractional indexing
- ⏳ Conflict detection
- ⏳ Branch-based merge

## Design Principles

1. **Convergence** - All replicas eventually reach the same state
2. **Commutativity** - Operations can be applied in any order
3. **Idempotency** - Re-applying operations is safe
4. **No Silent Data Loss** - Conflicts are explicit, not silently resolved
5. **Causal Consistency** - Operations respect causality
6. **Domain Invariants** - Preserve musical constraints (e.g., row duration)

## Key Architectural Decisions

- **Operation-based CRDT** (not state-based) for semantic operations
- **Vector clocks** for causality tracking (future: consider Hybrid Logical Clocks)
- **Fractional indexing** for stable positions
- **Tombstones** for deletions (never truly remove cells)
- **Conflict detection** rather than automatic LWW
- **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