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

<p><strong>Note:</strong> the following proof is indirect. And I am still interested in a direct proof.</p>

<blockquote>
  <p>Theorem: It is impossible to simulate sequential registers from causal registers.</p>
</blockquote>

<p>Proof: In the thesis [1], Kawash shows that causal consistency memory (with only $\texttt{read/write}$ operations) cannot solve mutual exclusion. However, <a href="http://en.wikipedia.org/wiki/Lamport&#39;s_bakery_algorithm" rel="nofollow">Lamport's bakery algorithm (wiki)</a>, when run on sequential consistency memories, solves mutual exclusion.</p>

<hr>

<p>[1] <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.7383&amp;rep=rep1&amp;type=pdf" rel="nofollow">Limitations and Capabilities of Weak Memory Consistency Systems</a> by Jalal Y. Kawash, PhD Thesis, 2000.</p>

CC BY-SA 3.0
2015-04-04T06:53:53.443Z
2015-04-04T16:10:22.140Z
2015-04-04T16:10:22.140Z
hengxin
<p><strong>Background:</strong> In distributed shared memory (DSM) model, the problem of <em>register simulations/constructions</em> 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].</p>

<p><strong>Question:</strong> </p>

<blockquote>
  <p>Is it possible to simulate sequential registers from causal ones in DSM model? And how to, if possible?</p>
</blockquote>

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

<hr>

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

<ds.algorithms><reference-request><dc.distributed-comp><concurrency>
How to simulate sequential registers from causal ones?
hengxin
# How to simulate sequential registers from causal ones?

(Asked by: username_0 on 2015-03-25)

**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].

**Question:**

> 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)

**Tags:** ds.algorithms, reference-request, dc.distributed-comp, concurrency

---

## 1 answers

### Answer by username_0 on 2015-04-04. Score: 0 | Accepted answer

**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)](http://en.wikipedia.org/wiki/Lamport's_bakery_algorithm), when run on sequential consistency memories, solves mutual exclusion.

---

[1] [Limitations and Capabilities of Weak Memory Consistency Systems](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.7383&rep=rep1&type=pdf) by Jalal Y. Kawash, PhD Thesis, 2000.


---

