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):

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

Read():

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

MWMR (Multi-Writer Multi-Reader)

Write(v):

1. Query phase: Read current max timestamp from a quorum
2. Write phase: Increment ts, write ⟨v, ts_new⟩ to a quorum
3. 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:

1. Total order on writes: Timestamps ⟨ts, wid⟩ form a strict total order
2. Quorum intersection witness: ∀ R, W quorums: ∃ server s ∈ R ∩ W
3. Freshness guarantee: Reader sees ts ≥ ts of most recent completed write (via intersection)
4. Write-back prevents inversion: Read returning v forces v to persist in a quorum before any subsequent read can return
5. Real-time respect: If op₁ completes before op₂ starts, linearization point of op₁ precedes op₂
6. 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)

1. Prime Path: No state revisited in skill invocation chain
2. Möbius Filter: Composite paths (backtracking) cancel via μ-inversion
3. GF(3) Conservation: Trit sum ≡ 0 (mod 3) across skill triplets
4. 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)