vclock.py
python
sha256:cf6265cea8c21d9228d90dec13ef6ec2dab5103d466db9cc4590681832de4bf8
docs(KD-STAGING): sync governance after KD-6b DONE
Human
13 days ago
| 1 | """Vector clock for causal ordering in distributed multi-agent writes. |
| 2 | |
| 3 | A vector clock (Lamport, 1978 / Fidge, 1988) tracks how many events each |
| 4 | agent has observed. Two clocks can be compared to determine whether one |
| 5 | *causally precedes* the other or whether they are *concurrent* (neither |
| 6 | dominates). |
| 7 | |
| 8 | This is the foundational primitive for all CRDT coordination in Muse: |
| 9 | |
| 10 | - :class:`LWWRegister` uses vector clock comparison to break same-timestamp |
| 11 | ties deterministically. |
| 12 | - :class:`RGA` uses ``agent_id`` for deterministic concurrent-insert ordering. |
| 13 | - The ``CRDTPlugin.join()`` protocol uses causal ordering to detect which |
| 14 | writes truly conflict vs. which are simply out-of-delivery-order. |
| 15 | |
| 16 | Public API |
| 17 | ---------- |
| 18 | - :class:`VClockDict` — ``TypedDict`` wire format ``{agent_id: count}``. |
| 19 | - :class:`VectorClock` — the clock itself, with ``increment``, ``merge``, |
| 20 | ``happens_before``, ``concurrent_with``, ``to_dict``, ``from_dict``. |
| 21 | """ |
| 22 | |
| 23 | from __future__ import annotations |
| 24 | |
| 25 | from typing import TypedDict |
| 26 | |
| 27 | type _CountMap = dict[str, int] |
| 28 | |
| 29 | |
| 30 | class VClockDict(TypedDict, total=False): |
| 31 | """Wire format for a vector clock — ``{agent_id: event_count}``. |
| 32 | |
| 33 | ``total=False`` because the presence of a key is meaningful (an absent key |
| 34 | is equivalent to the value ``0``). Serialise with :meth:`VectorClock.to_dict` |
| 35 | and deserialise with :meth:`VectorClock.from_dict`. |
| 36 | """ |
| 37 | |
| 38 | class VectorClock: |
| 39 | """Causal clock for distributed agent writes. |
| 40 | |
| 41 | Stores a mapping from agent identifiers (arbitrary strings) to the number |
| 42 | of events that agent has performed. An absent agent is equivalent to |
| 43 | count ``0``. |
| 44 | |
| 45 | Instances are **immutable** from the outside: every mutating method returns |
| 46 | a new :class:`VectorClock` rather than modifying ``self``. This makes |
| 47 | clocks safe to store as dict values without defensive copying. |
| 48 | |
| 49 | Lattice laws satisfied by :meth:`merge`: |
| 50 | - **Commutativity**: ``merge(a, b) == merge(b, a)`` |
| 51 | - **Associativity**: ``merge(merge(a, b), c) == merge(a, merge(b, c))`` |
| 52 | - **Idempotency**: ``merge(a, a) == a`` |
| 53 | """ |
| 54 | |
| 55 | def __init__(self, counts: _CountMap | None = None) -> None: |
| 56 | """Create a vector clock, optionally pre-populated from *counts*. |
| 57 | |
| 58 | Args: |
| 59 | counts: Initial ``{agent_id: count}`` mapping. Copied defensively. |
| 60 | """ |
| 61 | self._counts: _CountMap = dict(counts) if counts else {} |
| 62 | |
| 63 | # ------------------------------------------------------------------ |
| 64 | # Mutation (returns new clock) |
| 65 | # ------------------------------------------------------------------ |
| 66 | |
| 67 | def increment(self, agent_id: str) -> VectorClock: |
| 68 | """Return a new clock with ``agent_id``'s counter incremented by 1. |
| 69 | |
| 70 | Args: |
| 71 | agent_id: The agent performing an event. |
| 72 | |
| 73 | Returns: |
| 74 | A new :class:`VectorClock` with the updated count. |
| 75 | """ |
| 76 | new_counts = dict(self._counts) |
| 77 | new_counts[agent_id] = new_counts.get(agent_id, 0) + 1 |
| 78 | return VectorClock(new_counts) |
| 79 | |
| 80 | def merge(self, other: VectorClock) -> VectorClock: |
| 81 | """Return the least-upper-bound of ``self`` and *other*. |
| 82 | |
| 83 | For each agent, the result holds the *maximum* count seen in either |
| 84 | clock. This is the lattice join operation; it satisfies |
| 85 | commutativity, associativity, and idempotency. |
| 86 | |
| 87 | Args: |
| 88 | other: The clock to merge with. |
| 89 | |
| 90 | Returns: |
| 91 | A new :class:`VectorClock` holding per-agent maximums. |
| 92 | """ |
| 93 | all_agents = set(self._counts) | set(other._counts) |
| 94 | merged = { |
| 95 | agent: max(self._counts.get(agent, 0), other._counts.get(agent, 0)) |
| 96 | for agent in all_agents |
| 97 | } |
| 98 | return VectorClock(merged) |
| 99 | |
| 100 | # ------------------------------------------------------------------ |
| 101 | # Comparison |
| 102 | # ------------------------------------------------------------------ |
| 103 | |
| 104 | def happens_before(self, other: VectorClock) -> bool: |
| 105 | """Return ``True`` if ``self`` causally precedes *other*. |
| 106 | |
| 107 | ``a`` happens before ``b`` iff every agent counter in ``a`` is |
| 108 | ≤ the corresponding counter in ``b``, and at least one counter is |
| 109 | strictly less (i.e. ``a != b``). |
| 110 | |
| 111 | Args: |
| 112 | other: The clock to compare against. |
| 113 | |
| 114 | Returns: |
| 115 | ``True`` when ``self < other`` in causal order. |
| 116 | """ |
| 117 | all_agents = set(self._counts) | set(other._counts) |
| 118 | leq = all( |
| 119 | self._counts.get(agent, 0) <= other._counts.get(agent, 0) |
| 120 | for agent in all_agents |
| 121 | ) |
| 122 | return leq and not self.equivalent(other) |
| 123 | |
| 124 | def concurrent_with(self, other: VectorClock) -> bool: |
| 125 | """Return ``True`` if neither clock causally precedes the other. |
| 126 | |
| 127 | Two clocks are concurrent when each has at least one counter strictly |
| 128 | greater than the other's corresponding counter. This is the condition |
| 129 | that a CRDT ``join`` must handle: there is no causal order between the |
| 130 | two writes, so neither can be simply discarded. |
| 131 | |
| 132 | Args: |
| 133 | other: The clock to compare against. |
| 134 | |
| 135 | Returns: |
| 136 | ``True`` when ``self`` and *other* are incomparable. |
| 137 | """ |
| 138 | return not self.happens_before(other) and not other.happens_before(self) and not self.equivalent(other) |
| 139 | |
| 140 | # ------------------------------------------------------------------ |
| 141 | # Serialisation |
| 142 | # ------------------------------------------------------------------ |
| 143 | |
| 144 | def to_dict(self) -> _CountMap: |
| 145 | """Return a JSON-serialisable ``{agent_id: count}`` mapping. |
| 146 | |
| 147 | Returns: |
| 148 | A shallow copy of the internal counts dictionary. |
| 149 | """ |
| 150 | return dict(self._counts) |
| 151 | |
| 152 | @classmethod |
| 153 | def from_dict(cls, data: _CountMap) -> VectorClock: |
| 154 | """Reconstruct a :class:`VectorClock` from its wire representation. |
| 155 | |
| 156 | Args: |
| 157 | data: ``{agent_id: count}`` mapping as produced by :meth:`to_dict`. |
| 158 | |
| 159 | Returns: |
| 160 | A new :class:`VectorClock` with the given counts. |
| 161 | """ |
| 162 | return cls(data) |
| 163 | |
| 164 | # ------------------------------------------------------------------ |
| 165 | # Python dunder helpers |
| 166 | # ------------------------------------------------------------------ |
| 167 | |
| 168 | def equivalent(self, other: VectorClock) -> bool: |
| 169 | """Return ``True`` if both clocks represent identical causal state. |
| 170 | |
| 171 | Two clocks are equivalent when every agent's count is the same in both, |
| 172 | treating absent agents as count 0. This is a stricter check than |
| 173 | ``happens_before`` — it requires exact equality, not domination. |
| 174 | |
| 175 | Args: |
| 176 | other: The vector clock to compare against. |
| 177 | |
| 178 | Returns: |
| 179 | ``True`` when ``self`` and *other* are causally identical. |
| 180 | """ |
| 181 | all_agents = set(self._counts) | set(other._counts) |
| 182 | return all( |
| 183 | self._counts.get(a, 0) == other._counts.get(a, 0) |
| 184 | for a in all_agents |
| 185 | ) |
| 186 | |
| 187 | def __repr__(self) -> str: |
| 188 | return f"VectorClock({self._counts!r})" |
File History
1 commit
sha256:cf6265cea8c21d9228d90dec13ef6ec2dab5103d466db9cc4590681832de4bf8
docs(KD-STAGING): sync governance after KD-6b DONE
Human
13 days ago