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