Background: In distributed shared memory (DSM) model, the problem of register simulations/constructions is to simulate registers with certain characteristic out of registers with weaker features. For example, we can construct the strongest multi-writer multi-reader atomic $\texttt{read/write}$ registers from the weakest single-writer multi-reader safe ones [1].


Is it possible to simulate sequential registers from causal ones in DSM model? And how to, if possible?

I guess the answer is negative. However, I have no idea how to prove/disprove it (Googling does not help on this).

[1] The Art of Multiprocessor Programming. By Maurice Herlihy and Nir Shavit (Chapter 4)


1 Answer 1


Answer my own question: The answer is (probably; please let me know if I am wrong) negative: it is impossible to simulate sequential registers from causal registers.

Note: the following proof is indirect. And I am still interested in a direct proof.

Theorem: It is impossible to simulate sequential registers from causal registers.

Proof: In the thesis [1], Kawash shows that causal consistency memory (with only $\texttt{read/write}$ operations) cannot solve mutual exclusion. However, Lamport's bakery algorithm (wiki), when run on sequential consistency memories, solves mutual exclusion.

[1] Limitations and Capabilities of Weak Memory Consistency Systems by Jalal Y. Kawash, PhD Thesis, 2000.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.