mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
hanzoskills.com/llms.txt now opens with the install line, the API reference index and the company index, so an agent that lands on any one of the three can find the rest. robots.txt claimed 537 documents while llms.txt counts 920. The number is gone from robots.txt; llms.txt derives it. public/ is regenerated from scripts/site.py, which it had fallen behind: the copy-prompt menu and agent bar were in the generator and not in the committed pages. tests/site.mjs passes against the result. Co-authored-by: Hanzo Dev <[email protected]>
755 lines
32 KiB
HTML
755 lines
32 KiB
HTML
<!doctype html>
|
||
<html lang="en"><head>
|
||
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
|
||
<title>distributed-systems-interval-tree-clocks</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="alternate" type="text/markdown" href="/distributed-systems-interval-tree-clocks.md">
|
||
|
||
<link rel="icon" href="/favicon.svg">
|
||
<link rel="canonical" href="https://hanzoskills.com/distributed-systems-interval-tree-clocks">
|
||
</head>
|
||
<!-- Reading this with a machine? Every page here is also plain markdown.
|
||
This one: https://hanzoskills.com/distributed-systems-interval-tree-clocks.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-interval-tree-clocks</h1><p class="lede">Interval tree clocks for dynamic systems, scalable causality tracking, fork/join operations, avoiding process ID exhaustion</p><h1>Interval Tree Clocks</h1>
|
||
<p><strong>Scope</strong>: Interval tree clocks (ITC), dynamic causality, fork/join, scalable distributed time <strong>Lines</strong>: ~390 <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 systems with dynamic process creation</li><li>Avoiding vector clock ID exhaustion</li><li>Implementing fork/join parallelism tracking</li><li>Tracking causality without pre-assigned IDs</li><li>Building actor systems with spawn/terminate</li><li>Implementing causality in serverless functions</li><li>Managing ephemeral worker processes</li><li>Scaling beyond fixed process counts</li></ul>
|
||
<h2>Core Concepts</h2>
|
||
<h3>The Problem with Vector Clocks</h3>
|
||
<p><strong>Fixed process ID requirement</strong>:</p>
|
||
<pre><code>Vector Clock: {A:5, B:3, C:7}
|
||
↑ ↑ ↑
|
||
Pre-assigned IDs
|
||
|
||
Problems:
|
||
1. Must know all process IDs upfront
|
||
2. Adding new process → resize all vectors
|
||
3. Short-lived processes waste space
|
||
4. Can't handle dynamic fork/join</code></pre>
|
||
<p><strong>ID exhaustion</strong>:</p>
|
||
<pre><code>Serverless functions: 1000s of ephemeral workers
|
||
Actor systems: Actors spawn/terminate dynamically
|
||
Microservices: Containers scale up/down
|
||
|
||
Vector clock grows to 1000s of entries!</code></pre>
|
||
<h3>Interval Tree Clocks Solution</h3>
|
||
<p><strong>Key insight</strong>: Represent causality as intervals in ID space, not fixed IDs</p>
|
||
<pre><code>ITC = (id_interval, event_tree)
|
||
|
||
id_interval: Portion of ID space owned by this process
|
||
event_tree: Binary tree tracking causal events
|
||
|
||
Properties:
|
||
1. Fork: Split ID interval between processes
|
||
2. Join: Merge ID intervals when processes sync
|
||
3. Event: Increment counter in owned interval
|
||
4. O(log N) size for N events (not N processes!)</code></pre>
|
||
<p><strong>Visual</strong>:</p>
|
||
<pre><code>Process A owns [0, 1):
|
||
ITC_A = ([0, 1), tree)
|
||
|
||
A forks to create B:
|
||
ITC_A = ([0, 0.5), tree_a)
|
||
ITC_B = ([0.5, 1), tree_b)
|
||
|
||
A and B can fork further:
|
||
ITC_A1 = ([0, 0.25), ...)
|
||
ITC_A2 = ([0.25, 0.5), ...)</code></pre>
|
||
<hr>
|
||
<h2>Algorithm</h2>
|
||
<h3>Data Structures</h3>
|
||
<pre><code class="lang-python">from typing import Optional, Tuple
|
||
from dataclasses import dataclass
|
||
|
||
@dataclass
|
||
class IDInterval:
|
||
"""Interval in ID space [start, end)"""
|
||
start: float
|
||
end: float
|
||
|
||
def __repr__(self):
|
||
return f"[{self.start:.3f}, {self.end:.3f})"
|
||
|
||
def is_empty(self) -> bool:
|
||
return self.start >= self.end
|
||
|
||
def split(self) -> Tuple['IDInterval', 'IDInterval']:
|
||
"""Split interval in half"""
|
||
mid = (self.start + self.end) / 2
|
||
return IDInterval(self.start, mid), IDInterval(mid, self.end)
|
||
|
||
def merge(self, other: 'IDInterval') -> Optional['IDInterval']:
|
||
"""Merge adjacent intervals"""
|
||
if self.end == other.start:
|
||
return IDInterval(self.start, other.end)
|
||
elif other.end == self.start:
|
||
return IDInterval(other.start, self.end)
|
||
return None
|
||
|
||
class EventTree:
|
||
"""Binary tree tracking causal events"""
|
||
|
||
def __init__(self, value: int = 0, left: Optional['EventTree'] = None,
|
||
right: Optional['EventTree'] = None):
|
||
self.value = value
|
||
self.left = left
|
||
self.right = right
|
||
|
||
def is_leaf(self) -> bool:
|
||
return self.left is None and self.right is None
|
||
|
||
def __repr__(self):
|
||
if self.is_leaf():
|
||
return f"{self.value}"
|
||
return f"({self.value}, {self.left}, {self.right})"
|
||
|
||
def copy(self) -> 'EventTree':
|
||
"""Deep copy of tree"""
|
||
if self.is_leaf():
|
||
return EventTree(self.value)
|
||
return EventTree(
|
||
self.value,
|
||
self.left.copy() if self.left else None,
|
||
self.right.copy() if self.right else None
|
||
)
|
||
|
||
class ITC:
|
||
"""Interval Tree Clock"""
|
||
|
||
def __init__(self, interval: IDInterval, event: EventTree):
|
||
self.interval = interval
|
||
self.event = event
|
||
|
||
def __repr__(self):
|
||
return f"ITC({self.interval}, {self.event})"
|
||
|
||
@staticmethod
|
||
def seed() -> 'ITC':
|
||
"""Create initial ITC with full ID space"""
|
||
return ITC(IDInterval(0.0, 1.0), EventTree(0))
|
||
|
||
def copy(self) -> 'ITC':
|
||
"""Deep copy"""
|
||
return ITC(self.interval, self.event.copy())</code></pre>
|
||
<hr>
|
||
<h2>Core Operations</h2>
|
||
<h3>Event (Increment)</h3>
|
||
<pre><code class="lang-python">def event(self) -> 'ITC':
|
||
"""
|
||
Increment event counter in owned interval
|
||
|
||
Returns new ITC with incremented event
|
||
"""
|
||
def increment_tree(tree: EventTree, interval: IDInterval,
|
||
owned: IDInterval) -> EventTree:
|
||
if tree.is_leaf():
|
||
# Leaf covers owned interval - increment
|
||
return EventTree(tree.value + 1)
|
||
|
||
# Split interval and recurse
|
||
mid = (interval.start + interval.end) / 2
|
||
|
||
if owned.end <= mid:
|
||
# Owned interval in left half
|
||
left = increment_tree(tree.left, IDInterval(interval.start, mid), owned)
|
||
return EventTree(tree.value, left, tree.right.copy())
|
||
elif owned.start >= mid:
|
||
# Owned interval in right half
|
||
right = increment_tree(tree.right, IDInterval(mid, interval.end), owned)
|
||
return EventTree(tree.value, tree.left.copy(), right)
|
||
else:
|
||
# Owned interval spans both halves - should not happen in normal use
|
||
raise ValueError("Owned interval spans tree split")
|
||
|
||
new_event = increment_tree(self.event, IDInterval(0.0, 1.0), self.interval)
|
||
return ITC(self.interval, new_event)
|
||
|
||
# Usage
|
||
itc = ITC.seed()
|
||
print(f"Initial: {itc}") # ITC([0.000, 1.000), 0)
|
||
|
||
itc = itc.event()
|
||
print(f"After event: {itc}") # ITC([0.000, 1.000), 1)
|
||
|
||
itc = itc.event()
|
||
print(f"After event: {itc}") # ITC([0.000, 1.000), 2)</code></pre>
|
||
<h3>Fork (Split ID Space)</h3>
|
||
<pre><code class="lang-python">def fork(self) -> Tuple['ITC', 'ITC']:
|
||
"""
|
||
Split ITC into two independent ITCs
|
||
|
||
Returns (itc1, itc2) where:
|
||
- itc1 and itc2 can make independent events
|
||
- Together they cover original ID space
|
||
"""
|
||
# Split ID interval
|
||
left_interval, right_interval = self.interval.split()
|
||
|
||
# Clone event tree for both
|
||
left_itc = ITC(left_interval, self.event.copy())
|
||
right_itc = ITC(right_interval, self.event.copy())
|
||
|
||
return left_itc, right_itc
|
||
|
||
# Usage
|
||
itc = ITC.seed()
|
||
itc = itc.event() # ITC([0.000, 1.000), 1)
|
||
|
||
# Fork into two processes
|
||
itc_a, itc_b = itc.fork()
|
||
print(f"Process A: {itc_a}") # ITC([0.000, 0.500), 1)
|
||
print(f"Process B: {itc_b}") # ITC([0.500, 1.000), 1)
|
||
|
||
# Independent events
|
||
itc_a = itc_a.event() # A increments
|
||
itc_b = itc_b.event() # B increments (concurrent!)</code></pre>
|
||
<h3>Join (Merge Clocks)</h3>
|
||
<pre><code class="lang-python">def join(self, other: 'ITC') -> 'ITC':
|
||
"""
|
||
Merge two ITCs on synchronization
|
||
|
||
Returns new ITC with:
|
||
- Merged ID intervals
|
||
- Combined event trees (max of both)
|
||
"""
|
||
def merge_trees(tree1: EventTree, tree2: EventTree,
|
||
interval: IDInterval, int1: IDInterval,
|
||
int2: IDInterval) -> EventTree:
|
||
"""Merge two event trees"""
|
||
# Base case: both leaves
|
||
if tree1.is_leaf() and tree2.is_leaf():
|
||
return EventTree(max(tree1.value, tree2.value))
|
||
|
||
# Expand leaves to match structure
|
||
if tree1.is_leaf() and not tree2.is_leaf():
|
||
tree1 = EventTree(tree1.value, EventTree(0), EventTree(0))
|
||
if tree2.is_leaf() and not tree1.is_leaf():
|
||
tree2 = EventTree(tree2.value, EventTree(0), EventTree(0))
|
||
|
||
# Recursive merge
|
||
mid = (interval.start + interval.end) / 2
|
||
left_interval = IDInterval(interval.start, mid)
|
||
right_interval = IDInterval(mid, interval.end)
|
||
|
||
left = merge_trees(tree1.left, tree2.left, left_interval, int1, int2)
|
||
right = merge_trees(tree1.right, tree2.right, right_interval, int1, int2)
|
||
|
||
# Combine with max base
|
||
base = max(tree1.value, tree2.value)
|
||
return EventTree(base, left, right)
|
||
|
||
# Merge intervals
|
||
merged_interval = self._merge_intervals(self.interval, other.interval)
|
||
|
||
# Merge event trees
|
||
merged_event = merge_trees(
|
||
self.event, other.event,
|
||
IDInterval(0.0, 1.0),
|
||
self.interval, other.interval
|
||
)
|
||
|
||
return ITC(merged_interval, merged_event)
|
||
|
||
def _merge_intervals(self, int1: IDInterval, int2: IDInterval) -> IDInterval:
|
||
"""Merge two intervals (assumes adjacent or overlapping)"""
|
||
return IDInterval(min(int1.start, int2.start), max(int1.end, int2.end))
|
||
|
||
# Usage
|
||
itc_a, itc_b = ITC.seed().fork()
|
||
itc_a = itc_a.event() # A: 1
|
||
itc_b = itc_b.event().event() # B: 2
|
||
|
||
# Synchronize
|
||
itc_merged = itc_a.join(itc_b)
|
||
print(f"Merged: {itc_merged}") # Captures both histories</code></pre>
|
||
<hr>
|
||
<h2>Comparison Operations</h2>
|
||
<pre><code class="lang-python">def leq(self, other: 'ITC') -> bool:
|
||
"""
|
||
Check if self ≤ other (happens-before or concurrent)
|
||
|
||
Returns True if self's events are causally before or equal to other's
|
||
"""
|
||
def compare_trees(tree1: EventTree, tree2: EventTree) -> bool:
|
||
"""Check if tree1 ≤ tree2"""
|
||
if tree1.is_leaf() and tree2.is_leaf():
|
||
return tree1.value <= tree2.value
|
||
|
||
if tree1.is_leaf():
|
||
# Expand tree1 to match structure
|
||
return compare_trees(
|
||
EventTree(tree1.value, EventTree(0), EventTree(0)),
|
||
tree2
|
||
)
|
||
|
||
if tree2.is_leaf():
|
||
# Expand tree2 to match structure
|
||
return compare_trees(
|
||
tree1,
|
||
EventTree(tree2.value, EventTree(0), EventTree(0))
|
||
)
|
||
|
||
# Both internal nodes
|
||
return (tree1.value <= tree2.value and
|
||
compare_trees(tree1.left, tree2.left) and
|
||
compare_trees(tree1.right, tree2.right))
|
||
|
||
return compare_trees(self.event, other.event)
|
||
|
||
def concurrent(self, other: 'ITC') -> bool:
|
||
"""Check if self and other are concurrent"""
|
||
return not self.leq(other) and not other.leq(self)
|
||
|
||
# Usage
|
||
itc_a, itc_b = ITC.seed().fork()
|
||
itc_a = itc_a.event()
|
||
itc_b = itc_b.event()
|
||
|
||
print(itc_a.concurrent(itc_b)) # True - concurrent events
|
||
print(itc_a.leq(itc_b)) # False</code></pre>
|
||
<hr>
|
||
<h2>Practical Example: Actor System</h2>
|
||
<pre><code class="lang-python">class Actor:
|
||
"""Actor with ITC for causality tracking"""
|
||
|
||
def __init__(self, actor_id: str, itc: ITC):
|
||
self.actor_id = actor_id
|
||
self.itc = itc
|
||
self.mailbox = []
|
||
|
||
def send_message(self, recipient: 'Actor', msg):
|
||
"""Send message with current ITC"""
|
||
# Local event (sending)
|
||
self.itc = self.itc.event()
|
||
|
||
# Include ITC snapshot in message
|
||
recipient.receive_message(msg, self.itc.copy())
|
||
|
||
def receive_message(self, msg, sender_itc: ITC):
|
||
"""Receive message and update ITC"""
|
||
# Merge with sender's causality
|
||
self.itc = self.itc.join(sender_itc)
|
||
|
||
# Process message (local event)
|
||
self.itc = self.itc.event()
|
||
|
||
print(f"[{self.actor_id}] Received: {msg}, ITC: {self.itc}")
|
||
|
||
def spawn_child(self) -> 'Actor':
|
||
"""Spawn child actor with forked ITC"""
|
||
parent_itc, child_itc = self.itc.fork()
|
||
|
||
self.itc = parent_itc
|
||
child = Actor(f"{self.actor_id}.child", child_itc)
|
||
|
||
print(f"[{self.actor_id}] Spawned child with ITC: {child.itc}")
|
||
return child
|
||
|
||
# Usage Example
|
||
# Create initial actor
|
||
root = Actor("root", ITC.seed())
|
||
|
||
# Spawn children
|
||
child1 = root.spawn_child()
|
||
child2 = root.spawn_child()
|
||
|
||
# Send messages
|
||
root.send_message(child1, "Hello from root")
|
||
child1.send_message(child2, "Hello from child1")
|
||
child2.send_message(root, "Reply from child2")
|
||
|
||
# Spawn grandchild
|
||
grandchild = child1.spawn_child()
|
||
child1.send_message(grandchild, "Message to grandchild")</code></pre>
|
||
<hr>
|
||
<h2>Serverless Function Example</h2>
|
||
<pre><code class="lang-python">class ServerlessFunction:
|
||
"""Serverless function with ITC causality"""
|
||
|
||
def __init__(self, function_id: str):
|
||
self.function_id = function_id
|
||
self.itc = None # Assigned dynamically
|
||
|
||
def invoke(self, request, context_itc: Optional[ITC] = None):
|
||
"""Invoke function with optional causal context"""
|
||
# Initialize or fork ITC
|
||
if context_itc is None:
|
||
# First invocation
|
||
self.itc = ITC.seed()
|
||
else:
|
||
# Fork from context
|
||
_, self.itc = context_itc.fork()
|
||
|
||
# Process request (local event)
|
||
self.itc = self.itc.event()
|
||
|
||
print(f"[{self.function_id}] Processing request, ITC: {self.itc}")
|
||
|
||
# Return result with ITC
|
||
return {"result": "processed", "itc": self.itc}
|
||
|
||
def chain_invoke(self, next_function: 'ServerlessFunction', request):
|
||
"""Invoke next function in chain"""
|
||
# Pass ITC context
|
||
return next_function.invoke(request, self.itc)
|
||
|
||
# Usage: Serverless workflow
|
||
fn1 = ServerlessFunction("process-order")
|
||
fn2 = ServerlessFunction("send-email")
|
||
fn3 = ServerlessFunction("update-inventory")
|
||
|
||
# Cold start
|
||
result1 = fn1.invoke({"order_id": 123})
|
||
|
||
# Chain invocations (causality preserved)
|
||
result2 = fn1.chain_invoke(fn2, {"email": "[email protected]"})
|
||
result3 = fn1.chain_invoke(fn3, {"item_id": 456})
|
||
|
||
# Parallel invocations (concurrent)
|
||
fn4 = ServerlessFunction("analytics")
|
||
fn5 = ServerlessFunction("logging")
|
||
fn1.chain_invoke(fn4, {}) # Concurrent
|
||
fn1.chain_invoke(fn5, {}) # Concurrent</code></pre>
|
||
<hr>
|
||
<h2>Comparison: Vector Clocks vs ITC</h2>
|
||
<p>| Aspect | Vector Clocks | Interval Tree Clocks | |--------|--------------|---------------------| | <strong>Process IDs</strong> | Pre-assigned, fixed | Dynamic, allocated on demand | | <strong>Size</strong> | O(N) processes | O(log E) events | | <strong>Fork</strong> | Not supported | O(1) | | <strong>Join</strong> | Element-wise max | Tree merge O(log E) | | <strong>Event</strong> | O(1) increment | O(log E) tree update | | <strong>Comparison</strong> | O(N) | O(E) | | <strong>Dynamic systems</strong> | Poor fit | Excellent fit | | <strong>Memory</strong> | High for many processes | Low, scales with events |</p>
|
||
<p><strong>Space comparison</strong>:</p>
|
||
<pre><code>System with 1000 short-lived processes:
|
||
|
||
Vector Clock:
|
||
- 1000 entries × 8 bytes = 8KB per version
|
||
- 10 versions = 80KB
|
||
|
||
ITC:
|
||
- Tree depth ≈ log₂(1000) ≈ 10 levels
|
||
- ~20 nodes × 8 bytes = 160 bytes per version
|
||
- 10 versions = 1.6KB
|
||
|
||
Savings: ~98% reduction!</code></pre>
|
||
<hr>
|
||
<h2>Optimizations</h2>
|
||
<h3>Tree Normalization</h3>
|
||
<pre><code class="lang-python">def normalize_tree(tree: EventTree) -> EventTree:
|
||
"""
|
||
Normalize tree by lifting common values
|
||
|
||
(5, (5, (5, 0, 0))) → (10, 0, 0)
|
||
"""
|
||
if tree.is_leaf():
|
||
return tree
|
||
|
||
left = normalize_tree(tree.left) if tree.left else EventTree(0)
|
||
right = normalize_tree(tree.right) if tree.right else EventTree(0)
|
||
|
||
# Lift common value
|
||
if not left.is_leaf() or not right.is_leaf():
|
||
min_val = min(left.value, right.value)
|
||
if min_val > 0:
|
||
left = _subtract_tree(left, min_val)
|
||
right = _subtract_tree(right, min_val)
|
||
return EventTree(tree.value + min_val, left, right)
|
||
|
||
return EventTree(tree.value, left, right)
|
||
|
||
def _subtract_tree(tree: EventTree, value: int) -> EventTree:
|
||
"""Subtract value from tree"""
|
||
if tree.is_leaf():
|
||
return EventTree(max(0, tree.value - value))
|
||
return EventTree(
|
||
max(0, tree.value - value),
|
||
_subtract_tree(tree.left, value),
|
||
_subtract_tree(tree.right, value)
|
||
)</code></pre>
|
||
<h3>Interval Coalescing</h3>
|
||
<pre><code class="lang-python">def coalesce_intervals(itcs: list) -> ITC:
|
||
"""
|
||
Merge multiple ITCs with adjacent intervals
|
||
|
||
Useful after collecting IDs from terminated processes
|
||
"""
|
||
# Sort by interval start
|
||
sorted_itcs = sorted(itcs, key=lambda i: i.interval.start)
|
||
|
||
# Merge adjacent intervals
|
||
result = sorted_itcs[0]
|
||
for itc in sorted_itcs[1:]:
|
||
merged_interval = result.interval.merge(itc.interval)
|
||
if merged_interval:
|
||
result = ITC(merged_interval, result.event)
|
||
result = result.join(itc)
|
||
else:
|
||
# Non-adjacent, can't merge
|
||
pass
|
||
|
||
return result</code></pre>
|
||
<hr>
|
||
<h2>Testing ITC</h2>
|
||
<pre><code class="lang-python">import unittest
|
||
|
||
class TestITC(unittest.TestCase):
|
||
def test_event_increments(self):
|
||
"""Test that event increments counter"""
|
||
itc = ITC.seed()
|
||
itc = itc.event()
|
||
itc = itc.event()
|
||
|
||
# Should have incremented
|
||
self.assertEqual(itc.event.value, 2)
|
||
|
||
def test_fork_splits_interval(self):
|
||
"""Test that fork splits ID interval"""
|
||
itc = ITC.seed()
|
||
itc1, itc2 = itc.fork()
|
||
|
||
# Check intervals split
|
||
self.assertLess(itc1.interval.end, itc2.interval.start + 0.01)
|
||
self.assertGreater(itc1.interval.end, itc2.interval.start - 0.01)
|
||
|
||
def test_concurrent_after_fork(self):
|
||
"""Test that independent events after fork are concurrent"""
|
||
itc = ITC.seed()
|
||
itc1, itc2 = itc.fork()
|
||
|
||
itc1 = itc1.event()
|
||
itc2 = itc2.event()
|
||
|
||
# Should be concurrent
|
||
self.assertTrue(itc1.concurrent(itc2))
|
||
|
||
def test_join_merges(self):
|
||
"""Test that join merges causality"""
|
||
itc = ITC.seed()
|
||
itc1, itc2 = itc.fork()
|
||
|
||
itc1 = itc1.event()
|
||
itc2 = itc2.event()
|
||
|
||
# Join
|
||
merged = itc1.join(itc2)
|
||
|
||
# Merged should dominate both
|
||
self.assertTrue(itc1.leq(merged))
|
||
self.assertTrue(itc2.leq(merged))
|
||
|
||
def test_happens_before(self):
|
||
"""Test happens-before relationship"""
|
||
itc = ITC.seed()
|
||
itc1 = itc.event()
|
||
itc2 = itc1.event()
|
||
|
||
# itc1 happened before itc2
|
||
self.assertTrue(itc1.leq(itc2))
|
||
self.assertFalse(itc2.leq(itc1))</code></pre>
|
||
<hr>
|
||
<h2>Related Skills</h2>
|
||
<ul><li><code>distributed-systems-vector-clocks</code> - Fixed-process causality</li><li><code>distributed-systems-dotted-version-vectors</code> - Optimized vector clocks</li><li><code>distributed-systems-logical-clocks</code> - Lamport clocks</li><li><code>distributed-systems-crdt-fundamentals</code> - Causal CRDTs</li><li><code>distributed-systems-eventual-consistency</code> - Consistency models</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-interval-tree-clocks.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
||
</footer>
|
||
</div></body></html> |