Czy linearyzowalność jest równoważna z problemem konsensusu?

We wstępie tego artykułu Ostatecznie linearyzowalne obiekty wspólne (PODC'10) autorzy przedstawili następujące oświadczenie bez odniesień:

Linearyzowalność można jednak osiągnąć tylko wtedy, gdy możliwe jest rozwiązanie konsensusu.

Tutaj linearyzowalność jest najsilniejszą znaną właściwością spójności wspólnych obiektów, co zaproponowano w artykule Linearyzowalność: warunek poprawności dla współbieżnych obiektów .

Mylę się co do powyższego stwierdzenia z powodu następujących argumentów:

W artykule Solidnie dzieląc się pamięcią w systemach przekazywania wiadomości (JACM95) wiemy, że linearyzowalność można osiągnąć w systemie asynchronicznego przekazywania wiadomości, tolerując niewielką liczbę awarii procesowych:

Dowolny bez czekania algorytm oparty na atomowych rejestrach z wieloma czytnikami z pojedynczym zapisem może być automatycznie emulowany w systemach przekazywania wiadomości, pod warunkiem, że co najmniej większość procesorów nie jest wadliwa i pozostaje podłączona.

Z drugiej strony, dokument Niemożliwość rozproszonego konsensusu z jednym błędnym procesem (JACM85) udowodnił niemożliwość wyniku konsensusu nawet przy tylko jednej awarii procesu:

Problem konsensusu dotyczy asynchronicznego systemu procesów, z których niektóre mogą być zawodne. Problem polega na tym, że niezawodne procesy uzgadniają wartość binarną. W tym artykule pokazano, że każdy protokół tego problemu ma możliwość nieterminacji, nawet z jednym wadliwym procesem.

Czy możemy zatem dojść do następującego wniosku:

konsensus jest silniejszy niż linearyzowalność?

Co jest nie tak z moimi argumentami? Czy istnieją bezpośrednie odniesienia do wniosku o równoważności ?

Problem w tym, że się mylisz: „wiemy, że linearyzowalność można osiągnąć w systemie asynchronicznego przekazywania komunikatów, tolerując przy tym niewielką awarię procesu”. Nie wiemy tego, a tak naprawdę jest źle.

Cytat z artykułu JACM95 pokazuje, że rejestry z wieloma czytnikami z pojedynczym zapisem mogą być implementowane za pomocą przekazywania wiadomości. I tylko tego rodzaju rejestry lub inne obiekty, które mogą być zaimplementowane (biorąc pod uwagę niewielką liczbę awarii) z takich rejestrów. Dotyczy to na przykład rejestrów z wieloma czytnikami (MWMR).

Natomiast linearyzowalność nie ogranicza się do obiektów, które można zaimplementować przy użyciu rejestrów z wieloma czytnikami z pojedynczym zapisem. Jednym z przykładów takich obiektów są te, które obsługują (atomowe) operacje odczytu-modyfikacji-zapisu.

W rzeczywistości, jak zauważają Attiya i wsp. (Rozdział 7), takich obiektów nie można precyzyjnie zaimplementować w rejestrach MWMR, ponieważ pozwalają one na rozwiązanie konsensusu (por. Synchronizacja bez oczekiwania przez Herlihy), a zatem możliwość implementacji byłaby sprzeczna z wynikiem FLP.