Is linearizability equivalent to consensus problem?

Question

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?

Answer 1

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.