Теоретическая недостижимость консенсуса

У меня тут в бложеке несколько раз были споры о достижимости/недостижимости полной согласованности в асинхронных распределённых системах.

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

В литературе эта работа называется FLP result; клик по скриншоту – оригинальная работа 1985 года.

В оригинале длинновато и нудновато, но есть и покороче/подоступнее версия, написанная простым английским языком: http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/

Любопытно, что встречающееся мнение о том, что Google Spanner (замена BigTable) обеспечивает consistency и consensus во всех случаях, неверно – см оригинальную публикацию.

Spanner обеспечивает порядок с помощью таймтстампов и зависит от службы TrueTime, которая несмотря на колоссальные усилия по реализации всё же не даёт точный таймстамп, а даёт некоторый доверительный интервал.

В этой связи вопрос о том, что выбирать – eventual consistency или strong consistency – можно считать закрытым. Никакой другой, кроме eventual, в распределённых системах просто быть не может. Даже если по недоразумению её назвали “strong”.

UPD. Главный вывод из этого всего – строить распределённые системы надо сразу с учётом сбоев. Нужно предусматривать механику аудита и восстановления согласованности. Как минимум банки докомпьютерной эпохи прекрасно это умели на протяжении последних лет 800.

UPD2. Комменты закрыты по причине перехода на личности, а заодно уверенности некоторых инженеров в том, что «распределённая система» – это кластер, а вот пользователи вокруг кластера – не часть системы и их можно исключить из рассмотрения. Так вот – нельзя.