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


You might want to look at the work of Gadi Taubenfeld. Many of his papers deal with impacts of different progress conditions such as (generalized) wait-freedom or obstruction-freedom on the computability power of shared objects in distributed systems, which includes registers.

  • $\begingroup$ It is exactly what I am looking for. Great thanks. (I will accept it if no other better answers appear in a few days.) $\endgroup$ – hengxin Mar 17 '15 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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