17. Atomicity

Mar 10, 2021

Readers must write

Given:

• asynchronous distributed system with arbitrary delays
• uses message passing
  • reordering of messages due to asynchrony
  • no spontaneous messages
  • messages are eventually delivered
• crash prone (for $N$ servers $f<\frac{N}{2}$)
• want fault tolerance → require redundancy
• single-writer, multi-reader

When a server in this system boots it knows its initial state and nothing else. The server will use majorities $M_1\cup M_2$ to discover current state → majority intersection is non-empty.

writer:

• input: v:type, sequence_no: int = 0, accumulator: int = 0
• state: <ts:0, lv: type>

server:

• state: <ts, lv>

reader:

• state: ts:int, v:type, sequence_no: int = 0, accumulator: int = 0

init acc = 0;
ts++, seq++;

broadcast('W', v, ts, seq)  // to N servers
await acc > N/2:            // wait for majority response
  then return

upon recv(w_ack, s):
  if s == seq: acc++

upon recv('W', v, ts, seq):
  if server.ts > ts:
     server.ts = ts
     server.lv = v
  send(w_ack, seq)

upon recv('R', seq):
  send(r_ack, lv, ts, seq)

acc = 0, ts = 0, seq++

broadcast('R', seq)
await acc > N/2:
  acc = 0, seq++
  broadcast('W', lv, ts, seq)  // → "reader must write"
  await acc > N/2
  return lv

upon recv('r_ack', v, t, seq):
    if s == seq then
      acc++
      if t > ts:
        ts = t
        lv = v

Sequence number:

• messages may be reordered, this number will account for reordered messages
• Dutta & Guerraoui: (maybe this?)
  • if $R<\frac{S}{f}$
  • readers are inversely proportional to number of failures
  • $R<(S/S/2)=2$ → $R$ must be 1 (this is not practical)
  • we say "fast" algorithm if it does only 1 broadcast (not 2)
  • here "fast" means one-round broadcast

There is opportunity to optimize between broadcast & await, for example, can track which servers respond fast and prioritize those servers in the future.

Execution

execution means alternating sequence of states and actions, e.g. $s_0,a_1,s_1,a_2,s_2,a_3,\dots$ There is no parallelism in this sequence.

• writer does broadcast(...) → to S servers.
• communication channel state changes because it now includes the sent message
• adding messages to communication channel is visible to outside observer
• the sequence is ordered by timestamps → no parallelism
• every execution has interleaving semantics
• outside observer can see this interleaving with timestamps
• there are no infinite actions (no zeno)

Atomicity

Regarding read/write (RW) service, execution of RW is atomic is there exists a partial order (P.O.) on all completed operations such that:

1. P.O. respects real time; means if ${\pi }_1$ and ${\pi }_2$ are operations such that ${\pi }_1$ completes before ${\pi }_2$, then ${\pi }_2\nprec {\pi }_1$
2. All writes are totally ordered. If ${\omega }_1$ and ${\omega }_2$ are write operations then ${\omega }_1\prec {\omega }_2$ or ${\omega }_2\prec {\omega }_1$.
3. Reads are ordered so that $r_1$ returns value of immediately preceding write or the initial value if there is no such write

Example of partial order of messages:

Partial order is asymmetric and transitive

• if conditions 1, 2, 3 hold the implementation of R/W service is atomic if all executions are atomic
• empty execution is atomic by definition

Safety & Liveness

• safety means things never go wrong, or formally: no state is incorrect
• liveness means the system eventually does something good → eventually system returns messages

Note:

• Responding to messages is conditionless such that "something good"/response will occur without preconditions
• If some condition exists, it is called performance not liveness
• a R/W algorithm has a majority condition → this is an example of performance not liveness

Attya, Bar-Noy, Dolev (sp?) 1996: possibly the most important algorithm of R/W systems in a distributed setting. Pseudocode issue: timestamp, sequence number will eventually overflow; especially problematic if the init value is large and already close to overflow.