Одна из самых важных теорем в распределенных системах - C̶A̶P̶ FLP теорема.

Она строго доказывает, что невозможно достичь консенсуса, если:
🔸 Система асинхронна (что справедливо для реальных сетей)
🔸 Хоть один из узлов может отказать
🔸 Алгоритм детерминирован

И тут возникает вопрос - а как же алгоритмы консенсуса Paxos/Raft?

Paxos/Raft работают строго в рамках этой теоремы. У обоих алгоритмов существуют сценарии, при которых они не будут совершать прогресс, т.е. выбор одного значения на узлах никогда не завершится. Пофиксить это можно убрав какое-то условие из FLP, например детерминизм. Raft убирает детерменизм c помощью рандомных таймеров при выборе лидера, чтобы избегать таких сценариев.

Если вы вдруг придумали алгоритм консенсуса - найдите такое исполнение, при котором система не сможет совершать прогресс. Алгоритм консенсуса не может нарушать FLP теорему!

В общем, теорема не означает, что консенсус недостежим. Она лишь означает, что консенсус не всегда достежим/недостежим за детерминированное время. Это важно понимать.

#flp #theory