Back
+20 XP
Concept

Vector Clocks & Concurrent Event Detection

Lamport clocks cannot prove if two events happened concurrently ($a \parallel b$). A Vector Clock maintains an array of counters across all cluster nodes. Comparing vectors mathematically distinguishes between causal causality and conflicting concurrent writes 🔀🔍.

python
def check_causality(v1, v2):
    keys = set(v1) | set(v2)
    v1_le = all(v1.get(k, 0) <= v2.get(k, 0) for k in keys)
    v2_le = all(v2.get(k, 0) <= v1.get(k, 0) for k in keys)

    if v1_le and not v2_le:
        return "V1_HAPPENED_BEFORE_V2"
    if v2_le and not v1_le:
        return "V2_HAPPENED_BEFORE_V1"
    if v1_le and v2_le:
        return "IDENTICAL"
    return "CONCURRENT_CONFLICT 💥"

# Conflicting concurrent writes on partitioned nodes:
clock_a = {"node_1": 2, "node_2": 0}
clock_b = {"node_1": 0, "node_2": 2}
print(check_causality(clock_a, clock_b))

# 33. Vector Clocks & Concurrent Event Detection If two users update the same Google Doc or shopping cart offline at the same time, a single scalar timestamp cannot tell you they diverged without knowing about each other 🛑. ```python # Node A has seen 2 updates from A, 1 from B: {'A': 2, 'B': 1} # Node B has seen 1 update from A, 2 from B: {'A': 1, 'B': 2} # Neither vector dominates -> CONCURRENT! ``` ### Vector Clock Rules 1. **Dimension per Node**: Each node $k$ maintains vector $V$ where $V[k]$ is its own sequence number and $V[j]$ is its latest knowledge of node $j$'s clock. 2. **Local Advancement**: Before an internal event or write: $V_i[i] = V_i[i] + 1$. 3. **Merge Rule**: Upon receiving vector $W$ over the network: $$V_i[j] = \max(V_i[j], W[j]) \quad \forall j$$ followed by $V_i[i] = V_i[i] + 1$. 4. **Dominance**: $V_1 \le V_2 \iff V_1[k] \le V_2[k] \ \forall k$. If $V_1 \not\le V_2$ and $V_2 \not\le V_1$, the writes are mathematically concurrent and require a resolution strategy (such as CRDTs or application merge) 🔀. --- ### Interactive Pop-Quiz 🧠 #### What mathematical property indicates that two events with vector clocks $V_A$ and $V_B$ occurred concurrently ($V_A \parallel V_B$)? - [ ] Neither vector is strictly less-than-or-equal-to the other across all node dimensions ($V_A \not\le V_B$ and $V_B \not\le V_A$) 🔀 - [ ] Both vectors share the same hash value when encoded in JSON - [ ] The sum of elements in $V_A$ is an odd number while $V_B$ is even - [ ] The vectors have identical values on node index 0 --- ### Practical Challenge 🎯 Implement `is_concurrent(v1, v2)` that takes two dictionary clocks and returns `True` if neither vector dominates the other (i.e. neither `v1 <= v2` nor `v2 <= v1` for all keys), and `False` otherwise. Test with `{'A': 2, 'B': 1}` vs `{'A': 1, 'B': 2}` (concurrent) and `{'A': 1, 'B': 1}` vs `{'A': 2, 'B': 1}` (causal). Print the boolean results. <details> <summary>Solution</summary> ```python def is_concurrent(v1, v2): keys = set(v1) | set(v2) v1_le = all(v1.get(k, 0) <= v2.get(k, 0) for k in keys) v2_le = all(v2.get(k, 0) <= v1.get(k, 0) for k in keys) return not v1_le and not v2_le c1 = {"A": 2, "B": 1} c2 = {"A": 1, "B": 2} causal1 = {"A": 1, "B": 1} causal2 = {"A": 2, "B": 1} print(f"{is_concurrent(c1, c2)},{is_concurrent(causal1, causal2)}") ``` </details>

Checkpoint

What mathematical property indicates that two events with vector clocks VA and VB occurred concurrently? 🧠

Practice

Implement `is_concurrent(v1, v2)` that takes two dictionary clocks and returns `True` if neither vector dominates the other (i.e. neither `v1 <= v2` nor `v2 <= v1` for all keys), and `False` otherwise. Test with `{'A': 2, 'B': 1}` vs `{'A': 1, 'B': 2}` (concurrent) and `{'A': 1, 'B': 1}` vs `{'A': 2, 'B': 1}` (causal). Print the boolean results. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks