ABD: Atomic Register Emulation

Paper: Attiya, Bar-Noy, Dolev. Sharing memory robustly in message-passing systems. JACM 42(1):124-142, 1995.

Core Idea

ABD emulates a wait-free, atomic (linearizable) register on top of an asynchronous message-passing network tolerating f < n/2 crash failures. It is the foundational reduction from shared memory to message passing.

Three Structural Pillars

Pillar	Formal Object	Role
Quorum Intersection	Q subset of 2^Pi, forall Q1,Q2 in Q: Q1 intersect Q2 != empty	Any two majority sets overlap >= 1 correct process
Timestamps	(seq: N, writer_id: Pi) with lex order	Total order on writes; uniqueness across writers
Write-back	Reader propagates (v_max, t_max) to quorum	Upgrades regularity to atomicity; prevents new-old inversion

Protocol

SWMR (Single-Writer Multi-Reader)

WRITE(v):
  1. t <- t + 1                          [local]
  2. send WRITE(v, t) to all Pi           [1 RTT]
  3. wait for ACK from majority
  4. return OK
  -- Latency: 2d, Messages: O(n) --

READ():
  1. send READ(nonce) to all Pi           [1 RTT: query]
  2. wait for (v_i, t_i) from majority
  3. (v*, t*) <- argmax_t {responses}
  4. send WRITE(v*, t*) to all Pi         [1 RTT: write-back]
  5. wait for ACK from majority
  6. return v*
  -- Latency: 4d, Messages: O(n) --

MWMR Extension

Writers add a query phase to discover the current max timestamp:

WRITE(v):
  1. send READ(nonce) to all Pi           [1 RTT: query]
  2. wait for (v_i, t_i) from majority
  3. t <- (max(t_i.seq) + 1, my_id)      [local]
  4. send WRITE(v, t) to all Pi           [1 RTT: broadcast]
  5. wait for ACK from majority
  -- Latency: 4d, Messages: O(n) --

Read is identical to SWMR read (2 RTT).

Server Logic

on receive WRITE(v, t) from p:
  if t > local_t:
    local_v <- v; local_t <- t
  send ACK(v, t) to p

on receive READ(nonce) from p:
  send ACK(local_v, local_t, nonce) to p

Correctness Skeleton

Property	Argument
Termination	f<n/2 implies majority always alive; each phase needs only majority
Writes ordered	SWMR: monotone by single writer. MWMR: (seq,id) unique
Latest value	Query majority intersect write majority != empty implies sees latest ts
No new-old inversion	Write-back ensures majority holds t1; R2 majority overlaps implies t2 >= t1
Linearization	Order by ts; writes before reads at same ts
Necessity of f < n/2	Partition argument: two halves, cross-messages delayed

Complexity

Operation	RTTs	Messages	Latency
SWMR Write	1	O(n)	2d
SWMR Read	2	O(n)	4d
MWMR Write	2	O(n)	4d
MWMR Read	2	O(n)	4d

Extensions

Variant	Change	Trade-off
Fast reads	Skip write-back when no concurrent write	1-RTT reads; impossible for MWMR with n>5
Byzantine ABD	f < n/3 quorums + value validation + PKI	Tolerates arbitrary faults; 3x replication
Coded ABD	Erasure coding replaces full replication	Lower storage/bandwidth; same intersection property
Reconfigurable	Consensus on quorum membership changes	Dynamic membership (RAMBO protocol)

Key Insight

The write-back phase is what separates ABD from a naive quorum read. Without it, you get regular semantics (concurrent reads may disagree). With it, you get atomic/linearizable semantics. This single extra round-trip is the price of consistency.

References

• Attiya, Bar-Noy, Dolev. JACM 1995. DOI:10.1145/200836.200869
• Tseng et al. (Gus) SPAA 2023. DOI:10.1145/3558481.3591086
• Vukolic. Quorum Systems. Morgan & Claypool 2012

Concrete Affordance: Runnable ABD Simulation

Quick Start

# No external dependencies beyond Python 3.10+ standard library
python3 /Users/alice/v/asi/skills/abd/abd_sim.py

Simulation Script (abd_sim.py)

Save the following as /Users/alice/v/asi/skills/abd/abd_sim.py:

#!/usr/bin/env python3
"""
ABD SWMR atomic register simulation using threads + queues.
Spawns N=5 server processes (threads), 1 writer, 2 readers.
Demonstrates the write-back phase that upgrades regular → atomic semantics.
Tolerates f < n/2 = 2 crash failures.
"""

import threading
import queue
import time
import random
from dataclasses import dataclass, field
from typing import Any

N = 5  # number of servers
MAJORITY = N // 2 + 1

@dataclass
class TimestampedValue:
    value: Any = None
    seq: int = 0
    writer_id: int = 0

    def __lt__(self, other):
        return (self.seq, self.writer_id) < (other.seq, other.writer_id)

    def __repr__(self):
        return f"({self.value}, ts=({self.seq},{self.writer_id}))"


class ABDServer(threading.Thread):
    """Server process holding a local copy of the register."""

    def __init__(self, server_id: int, crash_after: int | None = None):
        super().__init__(daemon=True)
        self.server_id = server_id
        self.local = TimestampedValue()
        self.inbox = queue.Queue()
        self.crash_after = crash_after  # crash after N messages (None = never)
        self.msg_count = 0

    def run(self):
        while True:
            msg = self.inbox.get()
            self.msg_count += 1
            if self.crash_after and self.msg_count > self.crash_after:
                return  # simulate crash
            op, ts_val, reply_q = msg
            if op == "WRITE":
                if ts_val > self.local or (ts_val.seq == self.local.seq
                        and ts_val.writer_id == self.local.writer_id):
                    self.local = ts_val
                reply_q.put(("ACK", self.server_id, self.local))
            elif op == "READ":
                reply_q.put(("ACK", self.server_id, self.local))


def broadcast_and_collect(servers, op, ts_val, majority=MAJORITY):
    """Send op to all servers, wait for majority ACKs."""
    reply_q = queue.Queue()
    for s in servers:
        try:
            s.inbox.put_nowait((op, ts_val, reply_q))
        except Exception:
            pass  # server may have crashed
    acks = []
    deadline = time.monotonic() + 2.0
    while len(acks) < majority and time.monotonic() < deadline:
        try:
            acks.append(reply_q.get(timeout=0.1))
        except queue.Empty:
            pass
    return acks


def abd_write(servers, value, writer_state):
    """SWMR WRITE: increment local ts, broadcast, wait majority ACK."""
    writer_state.seq += 1
    writer_state.value = value
    ts = TimestampedValue(value, writer_state.seq, writer_state.writer_id)
    acks = broadcast_and_collect(servers, "WRITE", ts)
    assert len(acks) >= MAJORITY, f"Write failed: only {len(acks)} ACKs"
    print(f"  WRITE({value}) committed with ts=({ts.seq},{ts.writer_id}), "
          f"{len(acks)}/{N} ACKs")
    return ts


def abd_read(servers, reader_id):
    """SWMR READ: query majority, pick max ts, WRITE-BACK, return value."""
    # Phase 1: query
    acks = broadcast_and_collect(servers, "READ", TimestampedValue())
    assert len(acks) >= MAJORITY, f"Read query failed: only {len(acks)} ACKs"
    best = max((a[2] for a in acks), key=lambda tv: (tv.seq, tv.writer_id))

    # Phase 2: write-back (THIS is what makes it atomic, not just regular)
    wb_acks = broadcast_and_collect(servers, "WRITE", best)
    assert len(wb_acks) >= MAJORITY, f"Write-back failed: only {len(wb_acks)} ACKs"

    print(f"  READ by reader-{reader_id} => {best.value} "
          f"(ts=({best.seq},{best.writer_id}), "
          f"query={len(acks)}/{N}, wb={len(wb_acks)}/{N})")
    return best.value


def main():
    print(f"ABD Simulation: {N} servers, majority={MAJORITY}\n")

    # Spawn servers (crash server #4 after 3 messages to demonstrate fault tolerance)
    servers = [ABDServer(i, crash_after=3 if i == 4 else None) for i in range(N)]
    for s in servers:
        s.start()

    writer_state = TimestampedValue(None, 0, writer_id=0)

    # Writer writes 3 values
    print("--- Writer phase ---")
    for v in ["alpha", "beta", "gamma"]:
        abd_write(servers, v, writer_state)
        time.sleep(0.05)

    # Two readers read concurrently
    print("\n--- Reader phase (server #4 has crashed) ---")
    threads = []
    for rid in [1, 2]:
        t = threading.Thread(target=abd_read, args=(servers, rid))
        threads.append(t)
        t.start()
    for t in threads:
        t.join()

    # Both readers MUST return "gamma" (linearizability via write-back)
    print("\n--- Write after crash, demonstrating f<n/2 tolerance ---")
    abd_write(servers, "delta", writer_state)
    abd_read(servers, 3)

    print("\nDone. All operations linearizable despite 1 server crash.")


if __name__ == "__main__":
    main()

Using a Real Distributed Register Library

For production use beyond simulation:

# dslib — distributed systems simulation library (Python)
pip install dslib

# Or use etcd as a real linearizable register:
pip install etcd3

# etcd3 as a linearizable register (ABD-like semantics via Raft)
import etcd3
client = etcd3.client(host='localhost', port=2379)
client.put('/register/x', 'value')           # linearizable write
value, metadata = client.get('/register/x')   # linearizable read

Key Files

Path	Description
/Users/alice/v/asi/skills/abd/abd_sim.py	Runnable SWMR simulation (create from snippet above)
/Users/alice/v/asi/skills/abd/SKILL.md	This document