Skip to content

ABD Algorithm

  • ADB = Attiya, Bar-Noy, Dolev
  • Single-Writer Multi-Reader (SWMR) algorithm
  • uses replication to achieve fault tolerance and availability
  • tolerates minority failures of replica nodes
  • writes are fast (1 round)
  • reads take two rounds
  • each replica server maintains a local value and a tag (int)
  • tags serve as timestamps to order writes and to determine return values for reads

Specification

Writer

Operations have one phase that include a single communication round

  1. writer increments tad
  2. sends new value with tag to all servers
  3. awaits response from majority of servers
  4. terminates

img

Reader

Operations have two phases called query and propagation. Each phase is contains 1 communication round.

Query phase:

  1. query replica servers for values and tags
  2. await response from a majority of servers
  3. extract value corresponding to maximum tag

Propagation phase:

  1. propagate value and maximum tag to servers
  2. wait for response from majority of servers
  3. terminate

img

Server

  • each server maintains a replica of the shared object and associated tag
  • initial value of each replica is \(v_0\) and corresponding tag is 0
  • when server receives message from a reader in phase 1, it returns local value and tag
  • when server receives message from a reader in phase 2, it examines received tag and, if greater than local tag, it updates local value and tag; then it sends a response.

img

Analysis

Correctness

To prove correctness of ADB we need to show that any execution for \(|S| > 2f\) satisfies liveness (i.e. termination) and safety (i.e. atomicity) properties.

Termination is easy to show because of the constraint on the adversary and the fact that in read and write operations each communication round depends only on the correct majority of servers. Indeed, since \(|S| > 2f\), there is always a majority of servers that participate in any operation.

For any pair of operations, when one follows another, at least one correct server witnesses both operations because any two majority sets of servers have at least one server in common. This ensures that the second operation will always see the value that is at least as recent as that of the most recent preceding operation.

For a detailed proof, must prove that for each execution there exists a partial order on the set of operations that satisfy conditions A1, A2, A3 of atomicity.

Efficiency

  • \(d\) = maximum message delay, unknown to the algorithm
    • write latency is at most \(2d\)
    • read latency is at most \(4d\)
  • we assume local processing time is insignificant compared to the worst case messaging delays
  • on each round must process \(S/2\) messages; the remaining can be ignored or discarded

Multi-Writer ABD

  • single writer ABD can violate atomicity when number of writers is \(> 1\)
    • issues: writer tags are not unique
    • writers do not see each other
  • need to learn about latest write operation to have unique tags → read before write

Specification

Differences:

  • sequence numbers are used in ABD as tags to impose order on write operations
  • each writer tag is a tuple \(<seq, wid>\) (wid = writer id)
  • tags are ordered lexicographically, given \(t_i\) and \(t_j\) either:
    • \(t_i.seq > t_j.seq\) or
    • \(t_i.seq == t_j.seq\) and \(t_i.wid > t_j.wid\)
  • each write now performs two phases:
    1. query phase: query servers for the tag
    2. propagation phase: propagate new value and new tag (larger than any tag previously seen) to servers
  • reader, server implementations are the same except for the change in tag

img

Analysis

Termination property follows from same arguments as in single-writer ABD.

To prove correctness, prove that multi-writer ABD implements a MWMR read/write atomic object by showing conditions of atomicity (A1, A2, A3) hold.