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]>
589 lines
27 KiB
HTML
589 lines
27 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-consensus-paxos</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-consensus-paxos.md">
|
|
|
|
<link rel="icon" href="/favicon.svg">
|
|
<link rel="canonical" href="https://hanzoskills.com/distributed-systems-consensus-paxos">
|
|
</head>
|
|
<!-- Reading this with a machine? Every page here is also plain markdown.
|
|
This one: https://hanzoskills.com/distributed-systems-consensus-paxos.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-consensus-paxos</h1><p class="lede">Paxos consensus algorithm including Basic Paxos, Multi-Paxos, roles, phases, and practical implementations</p><h1>Paxos Consensus</h1>
|
|
<p><strong>Scope</strong>: Paxos algorithm, Basic Paxos, Multi-Paxos, roles, phases, practical implementations <strong>Lines</strong>: ~330 <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>Understanding consensus fundamentals</li><li>Implementing distributed agreement</li><li>Building fault-tolerant systems</li><li>Understanding Google Chubby, Spanner</li><li>Comparing with RAFT</li><li>Studying distributed systems theory</li><li>Building replicated state machines</li><li>Designing coordination services</li></ul>
|
|
<h2>Core Concepts</h2>
|
|
<h3>Paxos Overview</h3>
|
|
<p><strong>Goal</strong>: Achieve agreement on single value among distributed nodes despite failures</p>
|
|
<p><strong>Key properties</strong>:</p>
|
|
<ul><li>Safety: Only one value chosen</li><li>Liveness: Eventually chooses value (if majority available)</li><li>Fault tolerance: Tolerates f failures with 2f+1 nodes</li></ul>
|
|
<p><strong>Roles</strong> (nodes can have multiple roles):</p>
|
|
<pre><code>Proposer → Proposes values
|
|
Acceptor → Votes on proposals
|
|
Learner → Learns chosen value</code></pre>
|
|
<hr>
|
|
<h2>Basic Paxos</h2>
|
|
<h3>Two Phases</h3>
|
|
<p><strong>Phase 1: Prepare</strong></p>
|
|
<pre><code>Proposer → Acceptors: PREPARE(n)
|
|
Acceptors → Proposer: PROMISE(n, accepted_value)</code></pre>
|
|
<p><strong>Phase 2: Accept</strong></p>
|
|
<pre><code>Proposer → Acceptors: ACCEPT(n, value)
|
|
Acceptors → Learners: ACCEPTED(n, value)</code></pre>
|
|
<h3>Algorithm Details</h3>
|
|
<pre><code class="lang-python">class Proposer:
|
|
def __init__(self, node_id, acceptors):
|
|
self.node_id = node_id
|
|
self.acceptors = acceptors
|
|
self.proposal_number = 0
|
|
|
|
def propose(self, value):
|
|
"""Propose a value using Basic Paxos"""
|
|
# Generate unique proposal number (node_id + counter)
|
|
self.proposal_number += 1
|
|
n = (self.proposal_number, self.node_id)
|
|
|
|
# Phase 1: Prepare
|
|
promises = []
|
|
for acceptor in self.acceptors:
|
|
response = acceptor.prepare(n)
|
|
if response:
|
|
promises.append(response)
|
|
|
|
# Need majority
|
|
if len(promises) < len(self.acceptors) // 2 + 1:
|
|
return None # Failed to get majority
|
|
|
|
# Use highest-numbered accepted value, or our value if none
|
|
accepted_values = [p for p in promises if p.accepted_value is not None]
|
|
if accepted_values:
|
|
# Must use previously accepted value
|
|
value = max(accepted_values, key=lambda x: x.accepted_n).accepted_value
|
|
|
|
# Phase 2: Accept
|
|
accepts = 0
|
|
for acceptor in self.acceptors:
|
|
if acceptor.accept(n, value):
|
|
accepts += 1
|
|
|
|
# Chosen if majority accepted
|
|
if accepts >= len(self.acceptors) // 2 + 1:
|
|
return value
|
|
|
|
return None # Failed
|
|
|
|
|
|
class Acceptor:
|
|
def __init__(self):
|
|
self.promised_n = None # Highest n seen in prepare
|
|
self.accepted_n = None # Highest n accepted
|
|
self.accepted_value = None # Value accepted with accepted_n
|
|
|
|
def prepare(self, n):
|
|
"""Phase 1: Prepare"""
|
|
# Promise not to accept proposals < n
|
|
if self.promised_n is None or n > self.promised_n:
|
|
self.promised_n = n
|
|
return Promise(n, self.accepted_n, self.accepted_value)
|
|
return None # Reject (n too low)
|
|
|
|
def accept(self, n, value):
|
|
"""Phase 2: Accept"""
|
|
# Accept if n >= promised_n
|
|
if self.promised_n is None or n >= self.promised_n:
|
|
self.promised_n = n
|
|
self.accepted_n = n
|
|
self.accepted_value = value
|
|
return True
|
|
return False # Reject (n < promised_n)
|
|
|
|
|
|
class Promise:
|
|
def __init__(self, n, accepted_n, accepted_value):
|
|
self.n = n
|
|
self.accepted_n = accepted_n
|
|
self.accepted_value = accepted_value</code></pre>
|
|
<hr>
|
|
<h2>Multi-Paxos</h2>
|
|
<h3>Optimization for Multiple Values</h3>
|
|
<p><strong>Basic Paxos</strong>: Requires two round-trips per value (expensive!)</p>
|
|
<p><strong>Multi-Paxos</strong>: Elect stable leader, skip Phase 1 for subsequent proposals</p>
|
|
<pre><code class="lang-python">class MultiPaxos:
|
|
def __init__(self, nodes):
|
|
self.nodes = nodes
|
|
self.leader = None
|
|
self.log = [] # Sequence of chosen values
|
|
|
|
def elect_leader(self):
|
|
"""One-time leader election using Basic Paxos"""
|
|
self.leader = self.run_basic_paxos_for_leader()
|
|
|
|
def propose_value(self, value):
|
|
"""Leader proposes value (skips Phase 1)"""
|
|
if not self.leader or self.leader != self.node_id:
|
|
raise NotLeaderError()
|
|
|
|
# Leader can skip Phase 1 (already has promises)
|
|
# Phase 2 only: Accept
|
|
log_index = len(self.log)
|
|
accepts = 0
|
|
for acceptor in self.acceptors:
|
|
if acceptor.accept_at_index(log_index, self.leader_n, value):
|
|
accepts += 1
|
|
|
|
if accepts >= len(self.acceptors) // 2 + 1:
|
|
self.log.append(value)
|
|
return True
|
|
|
|
return False</code></pre>
|
|
<hr>
|
|
<h2>Paxos vs RAFT</h2>
|
|
<p>| Feature | Paxos | RAFT | |---------|-------|------| | <strong>Understandability</strong> | Complex, hard to grasp | Designed to be understandable | | <strong>Leader</strong> | Optional (Multi-Paxos adds leader) | Always has leader | | <strong>Log structure</strong> | Can have gaps | Contiguous log | | <strong>Membership changes</strong> | Challenging | Built-in mechanism | | <strong>Implementation</strong> | Many variations | Canonical algorithm | | <strong>Performance</strong> | Comparable | Comparable | | <strong>Adoption</strong> | Google (Chubby, Spanner) | etcd, Consul, more common |</p>
|
|
<hr>
|
|
<h2>Real-World Implementations</h2>
|
|
<h3>Google Chubby</h3>
|
|
<p><strong>Description</strong>: Distributed lock service using Paxos</p>
|
|
<pre><code class="lang-python"># Conceptual Chubby API
|
|
class Chubby:
|
|
def __init__(self, paxos_cluster):
|
|
self.paxos = paxos_cluster
|
|
|
|
def acquire_lock(self, lock_name, timeout=60):
|
|
"""Acquire distributed lock"""
|
|
# Use Paxos to agree on lock holder
|
|
value = {
|
|
'holder': self.client_id,
|
|
'timestamp': time.time(),
|
|
'timeout': timeout
|
|
}
|
|
|
|
success = self.paxos.propose(f'/locks/{lock_name}', value)
|
|
return success
|
|
|
|
def release_lock(self, lock_name):
|
|
"""Release distributed lock"""
|
|
self.paxos.propose(f'/locks/{lock_name}', None)</code></pre>
|
|
<h3>Google Spanner</h3>
|
|
<p><strong>Description</strong>: Globally-distributed database using Paxos for replication</p>
|
|
<p><strong>Paxos groups</strong>: Each shard replicated via Paxos</p>
|
|
<pre><code>Shard 1: Paxos(Replica A, B, C)
|
|
Shard 2: Paxos(Replica D, E, F)
|
|
Shard 3: Paxos(Replica G, H, I)</code></pre>
|
|
<p><strong>Transactions</strong>: Two-phase commit across Paxos groups</p>
|
|
<hr>
|
|
<h2>Practical Implementation</h2>
|
|
<h3>Python Example</h3>
|
|
<pre><code class="lang-python">import time
|
|
import random
|
|
from typing import Optional, Tuple
|
|
|
|
class PaxosNode:
|
|
"""Complete Paxos node (proposer + acceptor + learner)"""
|
|
|
|
def __init__(self, node_id, all_nodes):
|
|
self.node_id = node_id
|
|
self.all_nodes = all_nodes
|
|
|
|
# Proposer state
|
|
self.proposal_id = 0
|
|
|
|
# Acceptor state
|
|
self.promised_id = None
|
|
self.accepted_id = None
|
|
self.accepted_value = None
|
|
|
|
# Learner state
|
|
self.learned_value = None
|
|
|
|
def generate_proposal_id(self):
|
|
"""Generate unique, monotonically increasing proposal ID"""
|
|
self.proposal_id += 1
|
|
return (self.proposal_id, self.node_id)
|
|
|
|
def propose(self, value):
|
|
"""Propose a value (Phase 1 + Phase 2)"""
|
|
proposal_id = self.generate_proposal_id()
|
|
|
|
# Phase 1: Prepare
|
|
promises = []
|
|
for node in self.all_nodes:
|
|
response = node.receive_prepare(proposal_id)
|
|
if response:
|
|
promises.append(response)
|
|
|
|
# Check majority
|
|
if len(promises) < len(self.all_nodes) // 2 + 1:
|
|
return False # No majority, retry later
|
|
|
|
# Determine value to propose
|
|
highest_accepted = max(
|
|
[p for p in promises if p[1] is not None],
|
|
key=lambda x: x[0],
|
|
default=(None, None)
|
|
)
|
|
|
|
if highest_accepted[1] is not None:
|
|
value = highest_accepted[1] # Must use existing value
|
|
|
|
# Phase 2: Accept
|
|
accepts = 0
|
|
for node in self.all_nodes:
|
|
if node.receive_accept(proposal_id, value):
|
|
accepts += 1
|
|
# Learner: Learn value when accepted
|
|
node.learned_value = value
|
|
|
|
return accepts >= len(self.all_nodes) // 2 + 1
|
|
|
|
def receive_prepare(self, proposal_id):
|
|
"""Acceptor: Receive prepare request"""
|
|
if self.promised_id is None or proposal_id > self.promised_id:
|
|
self.promised_id = proposal_id
|
|
return (self.accepted_id, self.accepted_value)
|
|
return None
|
|
|
|
def receive_accept(self, proposal_id, value):
|
|
"""Acceptor: Receive accept request"""
|
|
if self.promised_id is None or proposal_id >= self.promised_id:
|
|
self.promised_id = proposal_id
|
|
self.accepted_id = proposal_id
|
|
self.accepted_value = value
|
|
return True
|
|
return False
|
|
|
|
# Usage
|
|
nodes = [PaxosNode(i, []) for i in range(5)]
|
|
for node in nodes:
|
|
node.all_nodes = nodes
|
|
|
|
# Multiple proposers competing
|
|
nodes[0].propose("value_A")
|
|
nodes[1].propose("value_B")
|
|
|
|
# Eventually one value wins
|
|
for node in nodes:
|
|
print(f"Node {node.node_id} learned: {node.learned_value}")</code></pre>
|
|
<hr>
|
|
<h2>Common Issues</h2>
|
|
<h3>Issue 1: Dueling Proposers</h3>
|
|
<p><strong>Problem</strong>: Two proposers keep interfering with each other</p>
|
|
<pre><code>Proposer A: PREPARE(1)
|
|
Proposer B: PREPARE(2) ← Invalidates A's prepare
|
|
Proposer A: PREPARE(3) ← Invalidates B's prepare
|
|
Proposer B: PREPARE(4) ← Invalidates A's prepare
|
|
... (infinite loop)</code></pre>
|
|
<p><strong>Solution</strong>: Randomized backoff or leader election (Multi-Paxos)</p>
|
|
<pre><code class="lang-python">def propose_with_backoff(self, value):
|
|
"""Propose with exponential backoff"""
|
|
backoff = 0.1
|
|
max_attempts = 10
|
|
|
|
for attempt in range(max_attempts):
|
|
if self.propose(value):
|
|
return True
|
|
|
|
# Exponential backoff with jitter
|
|
time.sleep(backoff * (1 + random.random()))
|
|
backoff = min(backoff * 2, 10)
|
|
|
|
return False</code></pre>
|
|
<h3>Issue 2: Learning the Chosen Value</h3>
|
|
<p><strong>Problem</strong>: Acceptors don't know when value is chosen</p>
|
|
<p><strong>Solutions</strong>:</p>
|
|
<p><strong>Option 1</strong>: Proposer notifies learners after Phase 2</p>
|
|
<pre><code class="lang-python">def notify_learners(self, value):
|
|
for learner in self.learners:
|
|
learner.learn(value)</code></pre>
|
|
<p><strong>Option 2</strong>: Acceptors notify distinguished learner</p>
|
|
<pre><code class="lang-python">def receive_accept(self, proposal_id, value):
|
|
if self.accept_proposal(proposal_id, value):
|
|
self.distinguished_learner.notify_accepted(proposal_id, value)</code></pre>
|
|
<p><strong>Option 3</strong>: Learners track acceptances</p>
|
|
<pre><code class="lang-python">class Learner:
|
|
def __init__(self, quorum_size):
|
|
self.acceptances = {} # proposal_id → {acceptor_ids}
|
|
self.quorum_size = quorum_size
|
|
|
|
def notify_accepted(self, acceptor_id, proposal_id, value):
|
|
if proposal_id not in self.acceptances:
|
|
self.acceptances[proposal_id] = (value, set())
|
|
|
|
self.acceptances[proposal_id][1].add(acceptor_id)
|
|
|
|
if len(self.acceptances[proposal_id][1]) >= self.quorum_size:
|
|
self.learned_value = value</code></pre>
|
|
<hr>
|
|
<h2>Testing Paxos</h2>
|
|
<pre><code class="lang-python">import unittest
|
|
|
|
class TestPaxos(unittest.TestCase):
|
|
def test_single_proposer(self):
|
|
"""Single proposer should succeed"""
|
|
nodes = [PaxosNode(i, []) for i in range(5)]
|
|
for node in nodes:
|
|
node.all_nodes = nodes
|
|
|
|
result = nodes[0].propose("value_A")
|
|
self.assertTrue(result)
|
|
|
|
# All nodes should learn the value
|
|
for node in nodes:
|
|
self.assertEqual(node.learned_value, "value_A")
|
|
|
|
def test_concurrent_proposers(self):
|
|
"""Concurrent proposers should reach consensus"""
|
|
nodes = [PaxosNode(i, []) for i in range(5)]
|
|
for node in nodes:
|
|
node.all_nodes = nodes
|
|
|
|
# Multiple proposers
|
|
nodes[0].propose("value_A")
|
|
nodes[1].propose("value_B")
|
|
|
|
# All nodes should agree (on one of the values)
|
|
learned_values = {node.learned_value for node in nodes if node.learned_value}
|
|
self.assertEqual(len(learned_values), 1) # All same
|
|
|
|
def test_node_failure(self):
|
|
"""Should tolerate minority node failures"""
|
|
nodes = [PaxosNode(i, []) for i in range(5)]
|
|
for node in nodes:
|
|
node.all_nodes = nodes
|
|
|
|
# Simulate 2 nodes failing (3/5 still available)
|
|
available_nodes = nodes[:3]
|
|
|
|
# Proposal should still succeed with majority
|
|
result = available_nodes[0].propose("value_A")
|
|
self.assertTrue(result)</code></pre>
|
|
<hr>
|
|
<h2>Performance Optimizations</h2>
|
|
<h3>1. Fast Paxos</h3>
|
|
<p><strong>Optimization</strong>: Skip proposer, clients send directly to acceptors</p>
|
|
<p><strong>Benefit</strong>: One fewer network round-trip when no conflicts</p>
|
|
<h3>2. Pipelining</h3>
|
|
<p><strong>Optimization</strong>: Proposer sends multiple proposals without waiting</p>
|
|
<p><strong>Benefit</strong>: Higher throughput</p>
|
|
<h3>3. Batching</h3>
|
|
<pre><code class="lang-python">def propose_batch(self, values):
|
|
"""Propose multiple values in single Paxos instance"""
|
|
batch_value = {
|
|
'type': 'batch',
|
|
'values': values
|
|
}
|
|
return self.propose(batch_value)</code></pre>
|
|
<hr>
|
|
<h2>Related Skills</h2>
|
|
<ul><li><code>distributed-systems-consensus-raft</code> - Alternative consensus algorithm</li><li><code>distributed-systems-leader-election</code> - Leader election patterns</li><li><code>distributed-systems-distributed-transactions</code> - Transaction protocols</li><li><code>distributed-systems-replication-strategies</code> - Data replication</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-consensus-paxos.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
|
</footer>
|
|
</div></body></html> |