<p>The thing you get wrong is "we know that linearizability can be achieved in the asynchronous message passing system, while tolerating a minority of process crashes." We don't know that, and in fact it is wrong. </p>

<p>What the quote from the JACM95 paper shows is that single-writer multi-reader registers can be implemented using message passing. And only this kind of registers, or any other objects that can be implemented (given a minority of crashes) from such registers. This includes for example multi-writer multi-reader registers (MWMR).</p>

<p>In contrast, <em>linearizability</em> is not limited to objects that can be implemented using single-writer multi-reader registers. One example of such objects are those that support (atomic) Read-Modify-Write operations. </p>

<p>In fact as Attiya et al point out (Section 7) such objects cannot be implemented by MWMR registers precicely because they allow solving consensus (cf. Wait-free synchronization by Herlihy) and thus implementability would contradict the FLP result. </p>

CC BY-SA 3.0
2013-12-29T03:07:19.043Z
Sorry for the delay. However, 1. Because *linearizability* is a **local property**, I don't think the number of objects concerned is the point. Could you please explain further? 2. What is your meaning of using "i.e.,"    to relate `atomicity of operations on a single object` with `sequential specifications are not violated`?
hengxin
CC BY-SA 3.0
2014-01-10T16:54:21.593Z
True. Let me think again....
Martin B.
CC BY-SA 3.0
2014-01-10T23:21:28.707Z
I've complemetely rewritten the answer... I think now it makes sense. Don't remember what I was thinking before.
Martin B.
CC BY-SA 3.0
2014-01-12T05:40:58.363Z
I think your current argument makes sense. Following your answer, I checked the paper ``Eventually Linearizable Shared Objects (PODC'10)`` and noticed that arbitrary objects (instead of only SWMR registers) were considered.
hengxin
CC BY-SA 3.0
2014-01-12T09:10:33.567Z
Thx for your attention and efforts. Are you working on distributed computing/concurrency theory? Then would you mind evaluating my another [problem: Atomic snapshot algorithms on tree-structured shared registers](http://cstheory.stackexchange.com/q/20357/12739)? Do you think it is a problem worth studying?
hengxin
CC BY-SA 3.0
2013-10-24T10:20:04.623Z
2014-01-10T23:20:39.187Z
2014-01-10T23:20:39.187Z
Martin B.
<p>In the introduction of this paper <a href="http://dl.acm.org/citation.cfm?id=1835723" rel="nofollow">Eventually Linearizable Shared Objects (PODC'10)</a>, the authors have presented the following statement without references:</p>

<blockquote>
  <p>Linearizability, however, can be achieved if and only if consensus can be solved.</p>
</blockquote>

<p>Here, linearizability is the strongest known consistency property of shared objects, which is proposed in the paper <a href="http://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf" rel="nofollow">Linearizability: A Correctness Condition for Concurrent Objects</a>. </p>

<p>I get confused about the above statement due to the following arguments:</p>

<p>In the paper <a href="http://www.cse.huji.ac.il/course/2004/dist/p124-attiya.pdf" rel="nofollow">Sharing Memory Robustly in Message-Passing Systems (JACM95)</a>, we know that linearizability can be achieved in the asynchronous message passing system, while tolerating a minority of process crashes:</p>

<blockquote>
  <p>Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems, provided that at least a majority of the processors are not faulty and remain connected.</p>
</blockquote>

<p>On the other hand, the paper <a href="http://macs.citadel.edu/rudolphg/csci604/ImpossibilityofConsensus.pdf" rel="nofollow">Impossibility of Distributed Consensus with One Faulty Process (JACM85)</a> has proved the impossibility result of consensus even with only one process crash:</p>

<blockquote>
  <p>The consensus problem  involves  an asynchronous system of processes, some of which  may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of  nontermination, even with only one faulty process.</p>
</blockquote>

<p>Therefore, can we reach the following conclusion:</p>

<blockquote>
  <p>consensus is <em>stronger</em> than linearizability?</p>
</blockquote>

<p>What is wrong with my arguments? Are there some direct references for the <em>equivalence</em> conclusion?</p>

CC BY-SA 3.0
2013-04-15T07:55:22.873Z
By far not an expert in distributed computing, but it seems to me that the reason you are able to derive your result is because of the assumptions made in the results in the JACM85 reference. Linearizability might be equivalent to consensus on a specific computation model, but this might not be the case if we greatly restrict our model of computation.
chazisop
<reference-request><dc.distributed-comp>
Is linearizability equivalent to consensus problem?
hengxin
# Is linearizability equivalent to consensus problem?

(Asked by: username_0 on 2013-04-15)

In the introduction of this paper [Eventually Linearizable Shared Objects (PODC'10)](http://dl.acm.org/citation.cfm?id=1835723), the authors have presented the following statement without references:

> Linearizability, however, can be achieved if and only if consensus can be solved.

Here, linearizability is the strongest known consistency property of shared objects, which is proposed in the paper [Linearizability: A Correctness Condition for Concurrent Objects](http://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf).

I get confused about the above statement due to the following arguments:

In the paper [Sharing Memory Robustly in Message-Passing Systems (JACM95)](http://www.cse.huji.ac.il/course/2004/dist/p124-attiya.pdf), we know that linearizability can be achieved in the asynchronous message passing system, while tolerating a minority of process crashes:

> Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems, provided that at least a majority of the processors are not faulty and remain connected.

On the other hand, the paper [Impossibility of Distributed Consensus with One Faulty Process (JACM85)](http://macs.citadel.edu/rudolphg/csci604/ImpossibilityofConsensus.pdf) has proved the impossibility result of consensus even with only one process crash:

> The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process.

Therefore, can we reach the following conclusion:

> consensus is *stronger* than linearizability?

What is wrong with my arguments? Are there some direct references for the *equivalence* conclusion?

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

> **Comments:**
> **username_1**: By far not an expert in distributed computing, but it seems to me that the reason you are able to derive your result is because of the assumptions made in the results in the JACM85 reference. Linearizability might be equivalent to consensus on a specific computation model, but this might not be the case if we greatly restrict our model of computation.  

---

## 1 answers

### Answer by username_2 on 2013-10-24. Score: 5 | Accepted answer

The thing you get wrong is "we know that linearizability can be achieved in the asynchronous message passing system, while tolerating a minority of process crashes." We don't know that, and in fact it is wrong.

What the quote from the JACM95 paper shows is that single-writer multi-reader registers can be implemented using message passing. And only this kind of registers, or any other objects that can be implemented (given a minority of crashes) from such registers. This includes for example multi-writer multi-reader registers (MWMR).

In contrast, *linearizability* is not limited to objects that can be implemented using single-writer multi-reader registers. One example of such objects are those that support (atomic) Read-Modify-Write operations.

In fact as Attiya et al point out (Section 7) such objects cannot be implemented by MWMR registers precicely because they allow solving consensus (cf. Wait-free synchronization by Herlihy) and thus implementability would contradict the FLP result.

> **Comments:**
> **username_0**: Sorry for the delay. However, 1. Because *linearizability* is a **local property**, I don't think the number of objects concerned is the point. Could you please explain further? 2. What is your meaning of using "i.e.,"    to relate `atomicity of operations on a single object` with `sequential specifications are not violated`?  
> **username_2**: True. Let me think again....  
> **username_2**: I've complemetely rewritten the answer... I think now it makes sense. Don't remember what I was thinking before.  
> **username_0**: I think your current argument makes sense. Following your answer, I checked the paper ``Eventually Linearizable Shared Objects (PODC'10)`` and noticed that arbitrary objects (instead of only SWMR registers) were considered.  
> **username_0**: Thx for your attention and efforts. Are you working on distributed computing/concurrency theory? Then would you mind evaluating my another [problem: Atomic snapshot algorithms on tree-structured shared registers](http://cstheory.stackexchange.com/q/20357/12739)? Do you think it is a problem worth studying?  

---

