Files
skills/public/distributed-systems-dotted-version-vectors.html
zeekay 747dafba10 Register WebMCP tools on every page, and name each page's twin from site.py
Every page now loads /webmcp.js, scripts/webmcp.ts with its types
stripped (npm run webmcp). Where the browser has document.modelContext
it registers two read-only tools: search_skills over the published
skills index, and get_skill, which returns a skill's markdown checked
against the index digest. The markdown alternate link moves from
build.py to site.py, so CI holds every page to it.

The API catalog gains the site itself (llms.txt and the skills index)
and hanzo.ai/agents; the live discovery check now fetches every
catalog link. tests/site.mjs drives the tools through a recording
modelContext, and checks a browser without one loads clean.
2026-10-26 20:57:05 -07:00

669 lines
31 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>distributed-systems-dotted-version-vectors</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/distributed-systems-dotted-version-vectors">
<link rel="alternate" type="text/markdown" href="/distributed-systems-dotted-version-vectors.md">
<script type="module" src="/webmcp.js"></script>
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/distributed-systems-dotted-version-vectors.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>distributed-systems-dotted-version-vectors</h1><p class="lede">Dotted version vectors for efficient sibling management, compact causality tracking, reducing metadata overhead compared to pure vector clocks</p><h1>Dotted Version Vectors</h1>
<p><strong>Scope</strong>: Dotted version vectors (DVV), sibling management, compact causality, optimized vector clocks <strong>Lines</strong>: ~380 <strong>Last Updated</strong>: 2025-10-27 <strong>Format Version</strong>: 1.0 (Atomic)</p>
<hr>
<h2>When to Use This Skill</h2>
<p>Activate this skill when:</p>
<ul><li>Building Riak-like key-value stores</li><li>Managing concurrent siblings efficiently</li><li>Reducing vector clock metadata overhead</li><li>Implementing optimized causality tracking</li><li>Avoiding false conflicts in distributed databases</li><li>Understanding Riak&#x27;s sibling resolution</li><li>Tracking only active writers</li><li>Optimizing storage for versioned data</li></ul>
<h2>Core Concepts</h2>
<h3>The Problem with Vector Clocks</h3>
<p><strong>Vector clocks grow unbounded</strong>:</p>
<pre><code>3 replicas write to same key:
Version 1: {A:1, B:0, C:0}
Version 2: {A:1, B:1, C:0}
Version 3: {A:1, B:1, C:1}
After 1000 writes across replicas:
{A:342, B:401, C:257} ← Metadata grows forever!</code></pre>
<p><strong>False siblings problem</strong>:</p>
<pre><code>Client writes via replica A:
Value 1: {A:1, B:0} &quot;Alice&quot;
Client writes again via A:
Value 2: {A:2, B:0} &quot;Alice Smith&quot;
Vector clocks say: NOT concurrent (A:1 &lt; A:2)
But system treats as siblings because client ID changed!</code></pre>
<h3>Dotted Version Vectors Solution</h3>
<p><strong>Key insight</strong>: Separate <strong>event</strong> (dot) from <strong>context</strong> (causal history)</p>
<pre><code>DVV = (dot, context)
dot = (node_id, counter) ← The write event
context = {node → counter} ← Causal history seen</code></pre>
<p><strong>Properties</strong>:</p>
<ol><li><strong>Compact</strong>: Only track active writes, not full history</li><li><strong>Precise</strong>: Distinguish updates from concurrent writes</li><li><strong>Efficient</strong>: Prune dominated versions automatically</li></ol>
<hr>
<h2>Algorithm</h2>
<h3>Data Structure</h3>
<pre><code class="lang-python">from typing import Dict, Tuple, Set
class Dot:
&quot;&quot;&quot;Single event identifier&quot;&quot;&quot;
def __init__(self, node_id: str, counter: int):
self.node_id = node_id
self.counter = counter
def __eq__(self, other):
return self.node_id == other.node_id and self.counter == other.counter
def __hash__(self):
return hash((self.node_id, self.counter))
def __repr__(self):
return f&quot;({self.node_id}:{self.counter})&quot;
class DottedVersionVector:
&quot;&quot;&quot;Dotted version vector for causality tracking&quot;&quot;&quot;
def __init__(self, node_id: str):
self.node_id = node_id
self.context = {} # node_id → max_counter seen
def new_dot(self) -&gt; Dot:
&quot;&quot;&quot;Create new dot for a write event&quot;&quot;&quot;
current = self.context.get(self.node_id, 0)
new_counter = current + 1
self.context[self.node_id] = new_counter
return Dot(self.node_id, new_counter)
def update_context(self, other_context: Dict[str, int]):
&quot;&quot;&quot;Merge contexts (element-wise max)&quot;&quot;&quot;
for node, counter in other_context.items():
self.context[node] = max(self.context.get(node, 0), counter)
def dot_in_context(self, dot: Dot) -&gt; bool:
&quot;&quot;&quot;Check if dot is in causal history&quot;&quot;&quot;
return self.context.get(dot.node_id, 0) &gt;= dot.counter
def is_concurrent(self, dot1: Dot, dot2: Dot, context1: Dict[str, int],
context2: Dict[str, int]) -&gt; bool:
&quot;&quot;&quot;Check if two dotted values are concurrent&quot;&quot;&quot;
# dot1 concurrent with dot2 if:
# - dot1 not in context2, AND
# - dot2 not in context1
dot1_seen = context2.get(dot1.node_id, 0) &gt;= dot1.counter
dot2_seen = context1.get(dot2.node_id, 0) &gt;= dot2.counter
return not dot1_seen and not dot2_seen</code></pre>
<h3>Versioned Value</h3>
<pre><code class="lang-python">class DottedValue:
&quot;&quot;&quot;Value with its causal dot&quot;&quot;&quot;
def __init__(self, value, dot: Dot, context: Dict[str, int]):
self.value = value
self.dot = dot
self.context = context.copy()
def __repr__(self):
return f&quot;DottedValue({self.value}, {self.dot}, ctx={self.context})&quot;
class DottedVersionStore:
&quot;&quot;&quot;Key-value store using dotted version vectors&quot;&quot;&quot;
def __init__(self, node_id: str):
self.node_id = node_id
self.dvv = DottedVersionVector(node_id)
self.store = {} # key → set of DottedValue
def write(self, key: str, value, context: Dict[str, int] = None):
&quot;&quot;&quot;Write value with new dot&quot;&quot;&quot;
# Update context with client&#x27;s causal knowledge
if context:
self.dvv.update_context(context)
# Create new dot for this write
dot = self.dvv.new_dot()
# Create dotted value
dotted = DottedValue(value, dot, self.dvv.context)
if key not in self.store:
self.store[key] = {dotted}
else:
# Remove values dominated by this write
self.store[key] = {
v for v in self.store[key]
if not self._is_dominated(v.dot, v.context, dot, dotted.context)
}
self.store[key].add(dotted)
return dotted
def read(self, key: str):
&quot;&quot;&quot;Read value(s) and context&quot;&quot;&quot;
if key not in self.store:
return [], {}
values = list(self.store[key])
# Compute merged context from all siblings
merged_context = {}
for v in values:
for node, counter in v.context.items():
merged_context[node] = max(merged_context.get(node, 0), counter)
return values, merged_context
def _is_dominated(self, dot1: Dot, ctx1: Dict[str, int],
dot2: Dot, ctx2: Dict[str, int]) -&gt; bool:
&quot;&quot;&quot;Check if (dot1, ctx1) is dominated by (dot2, ctx2)&quot;&quot;&quot;
# dot1 dominated if dot1 is in ctx2&#x27;s causal past
return ctx2.get(dot1.node_id, 0) &gt;= dot1.counter
def merge(self, key: str, remote_values: Set[DottedValue]):
&quot;&quot;&quot;Merge values from replica&quot;&quot;&quot;
if key not in self.store:
self.store[key] = remote_values
# Update context
for v in remote_values:
self.dvv.update_context(v.context)
return
# Merge local and remote
all_values = self.store[key] | remote_values
# Remove dominated versions
result = set()
for v1 in all_values:
dominated = False
for v2 in all_values:
if v1 != v2 and self._is_dominated(v1.dot, v1.context, v2.dot, v2.context):
dominated = True
break
if not dominated:
result.add(v1)
self.store[key] = result
# Update context from all values
for v in result:
self.dvv.update_context(v.context)</code></pre>
<hr>
<h2>Practical Example: Riak-Style KV Store</h2>
<h3>Complete Implementation</h3>
<pre><code class="lang-python">class RiakStyleKVStore:
&quot;&quot;&quot;Riak-inspired key-value store with DVV&quot;&quot;&quot;
def __init__(self, node_id: str, replicas: list):
self.node_id = node_id
self.replicas = replicas
self.store = DottedVersionStore(node_id)
def put(self, key: str, value, context: Dict[str, int] = None):
&quot;&quot;&quot;
Put value with optional causal context
Args:
key: The key to write
value: The value to write
context: Causal context from previous read (for updates)
Returns:
DottedValue with dot and updated context
&quot;&quot;&quot;
dotted = self.store.write(key, value, context)
# In real system: replicate to other nodes
# self._replicate_to_nodes(key, dotted)
return dotted
def get(self, key: str):
&quot;&quot;&quot;
Get value(s) for key
Returns:
(values, context) tuple
- If no conflict: single value
- If conflict: list of siblings
- context: causal context for next write
&quot;&quot;&quot;
values, context = self.store.read(key)
if not values:
return None, context
elif len(values) == 1:
return values[0].value, context
else:
# Multiple siblings - client must resolve
return [v.value for v in values], context
def resolve_siblings(self, key: str, resolved_value, context: Dict[str, int]):
&quot;&quot;&quot;
Resolve sibling conflict by writing resolution
Args:
key: The key with siblings
resolved_value: The resolved value
context: Context from get() that returned siblings
&quot;&quot;&quot;
return self.put(key, resolved_value, context)
# Usage Example
store_a = RiakStyleKVStore(&#x27;A&#x27;, [&#x27;A&#x27;, &#x27;B&#x27;, &#x27;C&#x27;])
store_b = RiakStyleKVStore(&#x27;B&#x27;, [&#x27;A&#x27;, &#x27;B&#x27;, &#x27;C&#x27;])
# Write on replica A
dotted1 = store_a.put(&#x27;user:1&#x27;, {&#x27;name&#x27;: &#x27;Alice&#x27;, &#x27;age&#x27;: 30})
print(f&quot;Write 1: {dotted1}&quot;)
# Output: DottedValue({&#x27;name&#x27;: &#x27;Alice&#x27;, &#x27;age&#x27;: 30}, (A:1), ctx={&#x27;A&#x27;: 1})
# Read and update on replica A
value, context = store_a.get(&#x27;user:1&#x27;)
dotted2 = store_a.put(&#x27;user:1&#x27;, {&#x27;name&#x27;: &#x27;Alice&#x27;, &#x27;age&#x27;: 31}, context)
print(f&quot;Update: {dotted2}&quot;)
# Output: DottedValue({&#x27;name&#x27;: &#x27;Alice&#x27;, &#x27;age&#x27;: 31}, (A:2), ctx={&#x27;A&#x27;: 2})
# Concurrent write on replica B (without seeing A&#x27;s updates)
dotted3 = store_b.put(&#x27;user:1&#x27;, {&#x27;name&#x27;: &#x27;Alice&#x27;, &#x27;email&#x27;: &#x27;[email protected]&#x27;})
print(f&quot;Concurrent write: {dotted3}&quot;)
# Output: DottedValue({...}, (B:1), ctx={&#x27;B&#x27;: 1})
# Merge at replica A
store_a.store.merge(&#x27;user:1&#x27;, {dotted3})
# Now reading shows siblings
siblings, ctx = store_a.get(&#x27;user:1&#x27;)
print(f&quot;Siblings detected: {siblings}&quot;)
# Output: [{&#x27;name&#x27;: &#x27;Alice&#x27;, &#x27;age&#x27;: 31}, {&#x27;name&#x27;: &#x27;Alice&#x27;, &#x27;email&#x27;: &#x27;[email protected]&#x27;}]
# Resolve conflict
merged = {&#x27;name&#x27;: &#x27;Alice&#x27;, &#x27;age&#x27;: 31, &#x27;email&#x27;: &#x27;[email protected]&#x27;}
resolved = store_a.resolve_siblings(&#x27;user:1&#x27;, merged, ctx)
print(f&quot;Resolved: {resolved}&quot;)
# Output: DottedValue({...}, (A:3), ctx={&#x27;A&#x27;: 3, &#x27;B&#x27;: 1})</code></pre>
<hr>
<h2>Comparison: Vector Clocks vs DVV</h2>
<h3>Memory Overhead</h3>
<pre><code class="lang-python"># Vector Clock approach
class VectorClockedValue:
def __init__(self, value, vc):
self.value = value
self.vector_clock = vc # Full vector: {A:342, B:401, C:257, ...}
# Dotted Version Vector approach
class DottedValue:
def __init__(self, value, dot, context):
self.value = value
self.dot = dot # Single dot: (A:343)
self.context = context # Pruned context: {A:342, B:401, C:257}
# Example after 1000 writes:
# VC: Every value carries full vector (3 nodes × 8 bytes × 1000 values = 24KB)
# DVV: Each value carries 1 dot + shared context (8 bytes + 24 bytes = 32 bytes)
# Savings: ~99% metadata reduction!</code></pre>
<h3>False Siblings</h3>
<pre><code class="lang-python"># Vector Clock: False siblings from client ID changes
vc_store = VectorClockStore(&#x27;A&#x27;, [&#x27;A&#x27;, &#x27;B&#x27;])
# Client 1 writes via A
vc_store.put(&#x27;key&#x27;, &#x27;v1&#x27;) # VC: {A:1, B:0}
# Same client writes again via A (new client connection)
vc_store.put(&#x27;key&#x27;, &#x27;v2&#x27;) # VC: {A:2, B:0}
# Result: May create siblings even though v2 supersedes v1!
# DVV: Correct handling
dvv_store = DottedVersionStore(&#x27;A&#x27;)
# Client writes
dotted1 = dvv_store.write(&#x27;key&#x27;, &#x27;v1&#x27;) # Dot: (A:1), ctx: {A:1}
# Client updates with context
dotted2 = dvv_store.write(&#x27;key&#x27;, &#x27;v2&#x27;, context={&#x27;A&#x27;: 1}) # Dot: (A:2), ctx: {A:2}
# Result: v1 correctly pruned, no false siblings</code></pre>
<hr>
<h2>Real-World Use Case: Riak</h2>
<p><strong>Riak&#x27;s DVV implementation</strong>:</p>
<pre><code class="lang-python">class RiakDVV:
&quot;&quot;&quot;Simplified Riak DVV logic&quot;&quot;&quot;
@staticmethod
def reconcile(local_values: Set[DottedValue],
remote_values: Set[DottedValue]) -&gt; Set[DottedValue]:
&quot;&quot;&quot;Riak&#x27;s sibling reconciliation&quot;&quot;&quot;
all_values = local_values | remote_values
# Compute global context
global_context = {}
for v in all_values:
for node, counter in v.context.items():
global_context[node] = max(global_context.get(node, 0), counter)
# Keep only values not in global context
survivors = set()
for v in all_values:
# Keep if dot not dominated by global context
if global_context.get(v.dot.node_id, 0) &lt; v.dot.counter:
survivors.add(v)
# Update context to global
v.context = global_context.copy()
return survivors if survivors else {max(all_values, key=lambda v: (v.dot.node_id, v.dot.counter))}
# Riak&#x27;s anti-entropy (read repair)
def read_repair(replicas: list, key: str) -&gt; DottedValue:
&quot;&quot;&quot;Fetch from multiple replicas and repair inconsistencies&quot;&quot;&quot;
all_values = set()
for replica in replicas:
values, _ = replica.read(key)
all_values.update(values)
# Reconcile
reconciled = RiakDVV.reconcile(all_values, set())
# Write reconciled values back to out-of-date replicas
for replica in replicas:
replica.store.store[key] = reconciled
return reconciled</code></pre>
<hr>
<h2>Performance Characteristics</h2>
<p>| Aspect | Vector Clocks | Dotted Version Vectors | |--------|--------------|----------------------| | <strong>Write latency</strong> | O(1) | O(1) | | <strong>Read latency</strong> | O(siblings) | O(siblings) | | <strong>Metadata size</strong> | O(N × writes) | O(N) + dot | | <strong>Sibling detection</strong> | Accurate | More accurate | | <strong>Pruning</strong> | Manual/periodic | Automatic | | <strong>False siblings</strong> | Common | Rare | | <strong>Memory</strong> | High (unbounded) | Low (bounded) |</p>
<p><strong>Space complexity</strong>:</p>
<ul><li>Vector clock: O(N) per version, grows with writes</li><li>DVV: O(N) shared context + O(1) per version</li></ul>
<hr>
<h2>Advanced: Causal Stability</h2>
<pre><code class="lang-python">class CausallyStableDVV:
&quot;&quot;&quot;DVV with causal stability detection&quot;&quot;&quot;
def __init__(self, node_id: str):
self.dvv = DottedVersionVector(node_id)
self.stable_context = {} # Causally stable events
def mark_stable(self, node_id: str, counter: int):
&quot;&quot;&quot;Mark events up to counter as stable&quot;&quot;&quot;
self.stable_context[node_id] = counter
def prune_stable(self, key: str):
&quot;&quot;&quot;Prune values dominated by stable context&quot;&quot;&quot;
if key not in self.store:
return
self.store[key] = {
v for v in self.store[key]
if self.stable_context.get(v.dot.node_id, 0) &lt; v.dot.counter
}
def compute_stability(self, replicas: list) -&gt; Dict[str, int]:
&quot;&quot;&quot;Compute causally stable frontier across replicas&quot;&quot;&quot;
# Stable = min counter across all replicas
stability = {}
for node_id in self.dvv.context.keys():
min_counter = min(
r.dvv.context.get(node_id, 0) for r in replicas
)
stability[node_id] = min_counter
return stability</code></pre>
<hr>
<h2>Testing DVV</h2>
<pre><code class="lang-python">import unittest
class TestDottedVersionVector(unittest.TestCase):
def test_update_supersedes(self):
&quot;&quot;&quot;Test that update with context supersedes previous&quot;&quot;&quot;
store = DottedVersionStore(&#x27;A&#x27;)
# Write
v1 = store.write(&#x27;key&#x27;, &#x27;value1&#x27;)
# Update with context
v2 = store.write(&#x27;key&#x27;, &#x27;value2&#x27;, context=v1.context)
# Only v2 should remain
values, _ = store.read(&#x27;key&#x27;)
self.assertEqual(len(values), 1)
self.assertEqual(values[0].value, &#x27;value2&#x27;)
def test_concurrent_creates_siblings(self):
&quot;&quot;&quot;Test that concurrent writes create siblings&quot;&quot;&quot;
store_a = DottedVersionStore(&#x27;A&#x27;)
store_b = DottedVersionStore(&#x27;B&#x27;)
# Concurrent writes
v1 = store_a.write(&#x27;key&#x27;, &#x27;value_a&#x27;)
v2 = store_b.write(&#x27;key&#x27;, &#x27;value_b&#x27;)
# Merge at A
store_a.merge(&#x27;key&#x27;, {v2})
# Should have siblings
values, _ = store_a.read(&#x27;key&#x27;)
self.assertEqual(len(values), 2)
def test_no_false_siblings(self):
&quot;&quot;&quot;Test that sequential updates don&#x27;t create false siblings&quot;&quot;&quot;
store = DottedVersionStore(&#x27;A&#x27;)
# First write
v1 = store.write(&#x27;key&#x27;, &#x27;v1&#x27;)
# Update with same key (simulating client getting context)
v2 = store.write(&#x27;key&#x27;, &#x27;v2&#x27;, context=v1.context)
# Should only have v2
values, _ = store.read(&#x27;key&#x27;)
self.assertEqual(len(values), 1)
self.assertEqual(values[0].value, &#x27;v2&#x27;)</code></pre>
<hr>
<h2>Related Skills</h2>
<ul><li><code>distributed-systems-vector-clocks</code> - Foundation causality tracking</li><li><code>distributed-systems-interval-tree-clocks</code> - Dynamic process IDs</li><li><code>distributed-systems-conflict-resolution</code> - Handling siblings</li><li><code>distributed-systems-eventual-consistency</code> - Consistency models</li><li><code>distributed-systems-crdt-fundamentals</code> - Convergent data structures</li></ul>
<hr>
<p><strong>Last Updated</strong>: 2025-10-27</p>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/distributed-systems-dotted-version-vectors.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>