<p>You might want to look at the <a href="http://dblp.uni-trier.de/pers/hd/t/Taubenfeld:Gadi" rel="nofollow">work</a> of Gadi Taubenfeld. Many of his papers deal with  <a href="http://link.springer.com/chapter/10.1007/978-3-642-10877-8_22" rel="nofollow">impacts of different progress conditions</a> such as (generalized) wait-freedom or <a href="http://dl.acm.org/citation.cfm?doid=1835698.1835709" rel="nofollow">obstruction-freedom</a> on the computability power of shared objects in distributed systems, which includes registers.</p>

CC BY-SA 3.0
2015-03-17T06:44:34.900Z
It is exactly what I am looking for. Great thanks. (I will accept it if no other better answers appear in a few days.)
hengxin
CC BY-SA 3.0
2015-03-17T03:07:37.900Z
2015-03-17T03:07:37.900Z
Peter
<p>I want to know more results about the <strong>computability power or limitations</strong> of shared $\texttt{read/write}$ registers/objects in distributed/concurrent computing theory.</p>

<p>Two typical examples are:</p>

<p>[1]. All types of atomic $\texttt{read/write}$ registers are equivalent in terms of computability: we can simulate the most complex one (i.e., multi-writer multi-reader multi-value atomic register) using the simplest ones (i.e., single-writer single-reader binary atomic registers).</p>

<p>[2]. Atomic $\texttt{read/write}$ registers have consensus number $1$. Therefore, from a set of atomic registers, it is <em>impossible</em> to construct a wait-free implementation of stack, queue, test&amp;set, compare&amp;swap, or memory-to-memory swap.</p>

<p>[1] <a href="http://dl.acm.org/citation.cfm?id=1734069" rel="nofollow">"The Art of Multiprocessor Programming (book abstract)"</a> by Maurice Herlihy and Nir Shavit, 2008.</p>

<p>[2] "Wait-Free Synchronization" by Maurice Herlihy, ACM Transactions on Programming Languages and Systems, 1991. </p>

<blockquote>
  <p>Do you know any other results about the <strong>computability power or limitations</strong> of shared $\texttt{read/write}$ registers in distributed/concurrent computing theory?</p>
</blockquote>

<p>Pointers to the literature would be appreciated.</p>

<reference-request><computability><dc.distributed-comp><concurrency>
Results about computability power or limitations of shared read/write registers
hengxin
# Results about computability power or limitations of shared read/write registers

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

I want to know more results about the **computability power or limitations** of shared $\texttt{read/write}$ registers/objects in distributed/concurrent computing theory.

Two typical examples are:

[1]. All types of atomic $\texttt{read/write}$ registers are equivalent in terms of computability: we can simulate the most complex one (i.e., multi-writer multi-reader multi-value atomic register) using the simplest ones (i.e., single-writer single-reader binary atomic registers).

[2]. Atomic $\texttt{read/write}$ registers have consensus number $1$. Therefore, from a set of atomic registers, it is *impossible* to construct a wait-free implementation of stack, queue, test&set, compare&swap, or memory-to-memory swap.

[1] ["The Art of Multiprocessor Programming (book abstract)"](http://dl.acm.org/citation.cfm?id=1734069) by Maurice Herlihy and Nir Shavit, 2008.

[2] "Wait-Free Synchronization" by Maurice Herlihy, ACM Transactions on Programming Languages and Systems, 1991.

> Do you know any other results about the **computability power or limitations** of shared $\texttt{read/write}$ registers in distributed/concurrent computing theory?

Pointers to the literature would be appreciated.

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

---

## 1 answers

### Answer by username_1 on 2015-03-17. Score: 3 | Accepted answer

You might want to look at the [work](http://dblp.uni-trier.de/pers/hd/t/Taubenfeld:Gadi) of Gadi Taubenfeld. Many of his papers deal with [impacts of different progress conditions](http://link.springer.com/chapter/10.1007/978-3-642-10877-8_22) such as (generalized) wait-freedom or [obstruction-freedom](http://dl.acm.org/citation.cfm?doid=1835698.1835709) on the computability power of shared objects in distributed systems, which includes registers.

> **Comments:**
> **username_0**: It is exactly what I am looking for. Great thanks. (I will accept it if no other better answers appear in a few days.)  

---

