Является ли линеаризуемость эквивалентной проблеме консенсуса?

Во введении к этой статье « В конечном итоге линеаризуемые общие объекты» (PODC'10) авторы представили следующее утверждение без ссылок:

Однако линеаризуемость может быть достигнута тогда и только тогда, когда можно достичь консенсуса.

Здесь линеаризуемость - это самое сильное известное свойство согласованности общих объектов, которое предлагается в статье « Линеаризуемость: условие корректности для параллельных объектов» .

Я запутался в приведенном выше утверждении из-за следующих аргументов:

В статье « Совместное использование памяти в системах передачи сообщений» (JACM95) мы знаем, что линеаризуемость может быть достигнута в асинхронной системе передачи сообщений, допуская при этом меньшее количество сбоев процессов:

Любой алгоритм без ожидания, основанный на атомарных регистрах с несколькими считывающими устройствами с одним записывающим устройством, может автоматически эмулироваться в системах передачи сообщений при условии, что по крайней мере большинство процессоров не являются неисправными и остаются подключенными.

С другой стороны, статья « Невозможность распределенного консенсуса с одним ошибочным процессом» (JACM85) доказала невозможность результата консенсуса даже при одном сбое процесса:

Проблема консенсуса включает асинхронную систему процессов, некоторые из которых могут быть ненадежными. Проблема заключается в том, чтобы надежные процессы согласовали двоичное значение. В этой статье показано, что каждый протокол для этой проблемы имеет возможность нетерминирования, даже с одним ошибочным процессом.

Следовательно, можем ли мы прийти к следующему выводу:

консенсус сильнее линеаризуемости?

Что не так с моими аргументами? Есть ли прямые ссылки для заключения об эквивалентности ?

Суть в том, что вы ошибаетесь: «мы знаем, что линеаризуемость может быть достигнута в асинхронной системе передачи сообщений, допуская при этом меньше сбоев процессов». Мы этого не знаем, и на самом деле это неправильно.

Цитата из статьи JACM95 показывает, что регистры с несколькими читателями с одним устройством записи могут быть реализованы с использованием передачи сообщений. И только такого рода регистры или любые другие объекты, которые могут быть реализованы (с учетом небольшого числа сбоев) из таких регистров. Это включает в себя, например, регистры с несколькими модулями чтения (MWMR).

Напротив, линеаризуемость не ограничивается объектами, которые могут быть реализованы с использованием регистров с несколькими считывателями с одним устройством записи. Одним из примеров таких объектов являются те, которые поддерживают (атомарные) операции чтения-изменения-записи.

Фактически, как указывают Аттия и др. (Раздел 7), такие объекты не могут быть реализованы с помощью регистров MWMR точно, потому что они позволяют решать задачи консенсуса (см. Синхронизацию без ожидания Герлихи) и, следовательно, реализуемость может противоречить результату FLP.