ABD Quorum-Based Registers Skill

ABD Quorum-Based Registers

Trit: 0 (ERGODIC) Domain: Distributed Systems / Shared Memory Emulation Principle: Linearizable read/write registers over message-passing via quorum intersection

Overview

ABD (Attiya, Bar-Noy, Dolev 1995) is the canonical protocol for emulating linearizable shared-memory registers over asynchronous message-passing networks. It decomposes consistency into three structural pillars and provides the tightest known RTT bounds for crash-tolerant atomic storage.

Three-Pillar Decomposition

Pillar 1: Quorum Intersection

Every read quorum Q_R and write quorum Q_W satisfy Q_R ∩ Q_W ≠ ∅. With majority quorums (|Q| = ⌊n/2⌋ + 1), this holds for any two quorums.

Sharp failure thresholds:

Crash failures: f < n/2
Byzantine failures: f < n/3

Pillar 2: Timestamps (Logical Clocks)

Each value is tagged with a monotonically increasing timestamp ⟨ts, writer_id⟩. Ties broken by writer ID give a total order on writes. Readers and writers always adopt the highest timestamp seen.

Pillar 3: Write-Back

After reading, the reader writes back the highest-timestamped value to a full quorum before returning. This prevents the new→old inversion that would violate linearizability.

Protocol Phases

SWMR (Single-Writer Multi-Reader)

Write(v):

ts ← ts + 1
Send ⟨WRITE, v, ts⟩ to all servers
Wait for ⌊n/2⌋ + 1 ACKs → return
Cost: 1 RTT, 2n messages

Read():

Query phase: Send ⟨READ⟩ to all, collect ⌊n/2⌋ + 1 replies → pick max-ts value
Write-back phase: Send ⟨WRITE-BACK, v_max, ts_max⟩ to all, wait for ⌊n/2⌋ + 1 ACKs
Return v_max
Cost: 2 RTT, 4n messages

MWMR (Multi-Writer Multi-Reader)

Write(v):

Query phase: Read current max timestamp from a quorum
Write phase: Increment ts, write ⟨v, ts_new⟩ to a quorum
Cost: 2 RTT, 4n messages

Read(): Same as SWMR read. Cost: 2 RTT, 4n messages

Complexity Table

| Operation | Variant | RTTs | Messages | Optimal? | |---------------|---------|------|----------|----------| | Write | SWMR | 1 | 2n | ✓ | | Read | SWMR | 2 | 4n | ✓ | | Write | MWMR | 2 | 4n | ✓ | | Read | MWMR | 2 | 4n | ✓ |

Linearizability Proof Skeleton

Six components to verify for any ABD-family protocol:

Total order on writes: Timestamps ⟨ts, wid⟩ form a strict total order
Quorum intersection witness: ∀ R, W quorums: ∃ server s ∈ R ∩ W
Freshness guarantee: Reader sees ts ≥ ts of most recent completed write (via intersection)
Write-back prevents inversion: Read returning v forces v to persist in a quorum before any subsequent read can return
Real-time respect: If op₁ completes before op₂ starts, linearization point of op₁ precedes op₂
Single-value per timestamp: ⟨ts, wid⟩ uniquely determines value (no ambiguity)

Sharp Impossibility Results

| Claim | Bound | |-------|-------| | Fast 1-RTT reads (MWMR) | Impossible if n > 5 (Dutta et al. 2004) | | Linearizability under partition | Impossible (CAP theorem) | | Wait-free consensus from registers | Impossible (FLP / consensus number = 1) | | Byzantine tolerance | Requires n ≥ 3f + 1 |

Extensions

| Extension | Key Idea | Reference | |-----------|----------|-----------| | Coded ABD | Replace replication with erasure codes; same quorum intersection, (1/r)× storage | Cadambe et al. 2015 | | RAMBO | Reconfigurable quorums via consensus on configuration changes | Lynch & Shvartsman 2002 | | Fast reads | 1-RTT reads when n ≤ 5 or with communication quorums | Dutta et al. 2004 | | Byzantine ABD | f < n/3, uses signed values + echo protocol | Malkhi & Reiter 1998 | | Multi-object | Atomic snapshots via collect-and-write-back on register arrays | AADGMS 1993 |

Shared-Memory ↔ Message-Passing Bridge

ABD is the constructive reduction: any shared-memory algorithm using read/write registers can be automatically emulated over message-passing with:

f < n/2 crash tolerance
O(n) message overhead per register operation
O(1) RTT overhead per operation

This means algorithms for snapshots, CAS, l-exclusion, etc. transfer with polynomial overhead, provided majority connectivity.

Relationship to Other Primitives

                    ┌─────────────┐
                    │  Consensus  │  (Paxos/Raft)
                    │  CN = ∞     │  leader + quorums
                    └──────┬──────┘
                           │ strictly stronger
                    ┌──────┴──────┐
                    │  ABD        │  linearizable R/W
                    │  CN = 1     │  quorums only
                    └──────┬──────┘
                           │ trades linearizability
                    ┌──────┴──────┐
                    │  CRDTs      │  eventual consistency
                    │  available  │  no quorum needed
                    └─────────────┘

Above: Consensus (Paxos/Raft) uses similar quorum ideas but adds leader election for state machine replication. Consensus number = ∞.
Below: CRDTs sacrifice linearizability for availability. No quorum intersection needed.
Beside: Coded storage uses the same intersection property with less replication overhead.

When to Use ABD

✅ Designing a distributed KV store or replicated register ✅ Proving linearizability of a new quorum protocol ✅ Choosing failure threshold (f < n/2 crash, f < n/3 Byzantine) ✅ Evaluating RTT/latency trade-offs for read/write operations ✅ Bridging shared-memory algorithms to message-passing ✅ Understanding where your protocol sits relative to consensus and CRDTs

When NOT to Use ABD

❌ Need leader-based state machine replication → use Paxos/Raft ❌ Availability-first / eventual consistency → use CRDTs ❌ Need compare-and-swap / consensus → ABD registers have consensus number 1

Integration with GF(3)

This skill participates in triadic composition:

Trit 0 (ERGODIC): Neutral — ABD occupies the middle of the consistency spectrum
Conservation: Σ trits ≡ 0 (mod 3) across skill triplets

Related Skills

consensus (trit 0) — strictly stronger primitive
crdt (trit 0) — trades consistency for availability
linearization — proof technique for ABD correctness
stability (trit +1) — quorum intersection as structural stability

Skill Name: abd-quorum-registers Type: Distributed Systems / Atomic Registers Trit: 0 (ERGODIC) GF(3): Conserved in triplet composition

Non-Backtracking Geodesic Qualification

Condition: μ(n) ≠ 0 (Möbius squarefree)

Prime Path: No state revisited in skill invocation chain
Möbius Filter: Composite paths (backtracking) cancel via μ-inversion
GF(3) Conservation: Trit sum ≡ 0 (mod 3) across skill triplets
Spectral Gap: Ramanujan bound λ₂ ≤ 2√(k-1) for k-regular expansion

Geodesic Invariant:
  ∀ path P: backtrack(P) = ∅ ⟹ μ(|P|) ≠ 0
  
Möbius Inversion:
  f(n) = Σ_{d|n} g(d) ⟹ g(n) = Σ_{d|n} μ(n/d) f(d)

Agent Skills: ABD Quorum-Based Registers

Install this agent skill to your local

Skill Files