[Solved]: Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems

Problem Detail: 

The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link failures.

Looking into the details of this algorithm (in Figure 2, page 133), I found that it implicitly assumes the "conditional write" primitives at the side of servers:

case received from w     <W, label_w>: label_j = max{label_w, label_j};                    send <ACK-W> to w; 

Here, the statement label_j = max{label_w, label_j} is equivalent to if (label_j < label_w) then label_j = label_w, requiring the variable label_j maintained by each process $j$ to be monotonic. This in turn needs the if-then "conditional write" primitive.

My first question is:

(1) Is this "conditional write" primitive necessary? Do you know any literature on emulations of atomic, SWMR registers without such primitives?

---

In the last section of the same paper, titled "Discussion and Further Research", the authors mentioned the emulations of stronger shared memory primitives in message-passing systems in presence of failures. One typical example is read-modify-write (RMW).

My second question is:

(2) Do you know any literature on the emulations of RMW-like primitives?

Google search and a quick glance over the "cited by" papers do not bring me anything specific.

Asked By : hengxin

Answered By : David Cary

Partial answer:

... if (label_j < label_w) then label_j = label_w

Is this "conditional write" primitive necessary?

Are you asking "Does this processor have to act 'as if' that test-and-assign was a single atomic instruction, so every message this processor sends to any other processor seems to show that the internal label_j variable always increases monotonically?"

Yes, from the outside, the processor must act "as if" the internal label_j value increases atomically and monotonically.

Are you asking "Does this processor need to actually modify label_j atomically?"

No. There are several ways to arrange things such that the updates appear, from the outside, to increment label_j atomically, even though the actual code that processor runs internally uses normal non-atomic sequences of instructions that (a) test the condition, (b) choose to branch, and then (c) update the value of label_j, while allowing lots of other stuff to interrupt the processor and modify that processor's memory between 'a' and 'b' and 'c'.

The simplest way is for that processor to be a uniprocessor that always processes incoming messages one at a time -- it buffers up messages from all other processors in a FIFO queue, chooses the oldest complete message (if any) from the queue to process, and otherwise doesn't even look at any incoming message until after it has finished dealing with the chosen message.

My understanding is that, in the systems described by that paper, no other processor can directly read the internal state of the label_j variable inside that processor.

Do you know any literature on the emulations of RMW-like primitives?

I was fascinated by Marice Herlihy's 1991 proof that: The atomic compare-and-swap instruction can emulate atomic-read, atomic-write, and fetch-and-add, but even if a CPU has atomic-read, atomic-write, and fetch-and-add, it can't emulate atomic compare-and-swap.

I am looking forward to reading a more complete answer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30059

3.2K people like this

 Download Related Notes/Documents