abd
Installation
SKILL.md
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 |