In the introduction of this paper Eventually Linearizable Shared Objects (PODC'10), 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.

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

In the paper Sharing Memory Robustly in Message-Passing Systems (JACM95), 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) 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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – chazisop
    Apr 15 '13 at 7:55

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.

  • $\begingroup$ 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? $\endgroup$
    – hengxin
    Dec 29 '13 at 3:07
  • $\begingroup$ True. Let me think again.... $\endgroup$
    – Martin B.
    Jan 10 '14 at 16:54
  • $\begingroup$ I've complemetely rewritten the answer... I think now it makes sense. Don't remember what I was thinking before. $\endgroup$
    – Martin B.
    Jan 10 '14 at 23:21
  • $\begingroup$ 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. $\endgroup$
    – hengxin
    Jan 12 '14 at 5:40
  • $\begingroup$ 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? Do you think it is a problem worth studying? $\endgroup$
    – hengxin
    Jan 12 '14 at 9:10

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.