crdt-music-rga.md
markdown
| 1 | # Voice-Aware Music RGA |
| 2 | |
| 3 | ## Status |
| 4 | |
| 5 | **Experimental** — not wired into the production merge path. This module |
| 6 | (`muse/plugins/midi/_crdt_notes.py`) exists to: |
| 7 | |
| 8 | 1. Demonstrate commutative concurrent note editing. |
| 9 | 2. Benchmark voice-aware RGA vs. LSEQ and standard three-way merge. |
| 10 | 3. Serve as the implementation foundation for a future live collaboration layer. |
| 11 | |
| 12 | ## Why standard RGA is wrong for music |
| 13 | |
| 14 | Standard RGA (Roh et al., 2011) orders concurrent insertions at the same |
| 15 | position lexicographically by op_id. Two agents inserting a bass note and a |
| 16 | soprano note at the same beat would have their pitches interleaved |
| 17 | arbitrarily — soprano might appear before bass, producing voice crossings that |
| 18 | are musicologically nonsensical. |
| 19 | |
| 20 | ## Music-RGA position key |
| 21 | |
| 22 | `NotePosition` is a `NamedTuple` with four fields that are compared in order: |
| 23 | |
| 24 | ``` |
| 25 | NotePosition = (measure, beat_sub, voice_lane, op_id) |
| 26 | ``` |
| 27 | |
| 28 | | Field | Purpose | |
| 29 | |-------|---------| |
| 30 | | `measure` | 1-indexed bar number | |
| 31 | | `beat_sub` | Tick offset within the bar | |
| 32 | | `voice_lane` | 0=bass, 1=tenor, 2=alto, 3=soprano — orders by register | |
| 33 | | `op_id` | UUID4 tie-break for concurrent edits in the same voice | |
| 34 | |
| 35 | At the same `(measure, beat_sub)`, notes are ordered by voice lane — bass |
| 36 | before treble — preventing voice crossings regardless of insertion order. |
| 37 | |
| 38 | ## CRDT laws |
| 39 | |
| 40 | The three lattice laws hold: |
| 41 | |
| 42 | 1. **Commutativity**: `merge(a, b).to_sequence() == merge(b, a).to_sequence()` |
| 43 | 2. **Associativity**: `merge(merge(a, b), c) == merge(a, merge(b, c))` |
| 44 | 3. **Idempotency**: `merge(a, a).to_sequence() == a.to_sequence()` |
| 45 | |
| 46 | Verified by `tests/test_crdt.py`. |
| 47 | |
| 48 | ## Tombstone semantics |
| 49 | |
| 50 | Deleted entries are tombstoned (marked `tombstone=True`) rather than removed. |
| 51 | This is standard RGA: the tombstone ensures that the deleted entry's position |
| 52 | remains stable for other replicas that may have concurrent insertions relative |
| 53 | to it. In the join operation, **tombstone wins**: if either replica has |
| 54 | deleted an entry, the merged result considers it deleted. |
| 55 | |
| 56 | ## Voice lane assignment |
| 57 | |
| 58 | Automatic voice lane assignment uses a coarse tessiture model: |
| 59 | |
| 60 | | MIDI pitch range | Voice lane | Label | |
| 61 | |-----------------|-----------|-------| |
| 62 | | 0–47 | 0 | Bass | |
| 63 | | 48–59 | 1 | Tenor | |
| 64 | | 60–71 | 2 | Alto | |
| 65 | | 72–127 | 3 | Soprano | |
| 66 | |
| 67 | Agents performing explicit voice separation can override `voice_lane` when |
| 68 | calling `MusicRGA.insert()`. |
| 69 | |
| 70 | ## Relationship to the commit DAG |
| 71 | |
| 72 | At commit time, `MusicRGA.to_domain_ops(base_sequence)` translates the CRDT |
| 73 | state into canonical `InsertOp` / `DeleteOp` entries for storage in the commit |
| 74 | record. The CRDT state itself is ephemeral — not stored in the object store. |
| 75 | |
| 76 | ## Related files |
| 77 | |
| 78 | | File | Role | |
| 79 | |------|------| |
| 80 | | `muse/plugins/midi/_crdt_notes.py` | `NotePosition`, `RGANoteEntry`, `MusicRGA` | |
| 81 | | `tests/test_crdt.py` | CRDT law verification + unit tests | |
| 82 | | `tools/benchmark.py` | RGA throughput benchmark | |