Описание тега consensus

В контексте распределенных вычислений консенсус является фундаментальной проблемой, которая привлекла пристальное внимание в исследованиях, поскольку проблема, такая как атомарные регистры сравнения и замены (CAS) или атомарная фиксация транзакции, может быть сведена к ней. Кроме того, консенсус создает основу для реализации таких приложений, как выборы лидера, синхронизация часов и репликация конечного автомата. Хотя проблему можно объяснить простыми словами, решить ее гораздо труднее и при определенных обстоятельствах даже невозможно.

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

• потеря пакетов
• дублирование / переупорядочивание пакетов
• произвольная отложенная доставка пакетов
• пауза или даже сбой узла

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

• Соглашение: все решения исправных процессоров должны быть одинаковыми.
• Целостность: ни один узел не решает дважды.
• Валидность: если все узлы выбирают значение v, тогда было предложено v.
• Завершение: каждый исправный узел должен в конечном итоге выбрать значение.

Завершение - это свойство живучести и требует, чтобы алгоритм был отказоустойчивым. Без удовлетворения этого свойства алгоритм мог бы просто использовать предопределенного лидера, который определяет значения (например, 2PC). Но если лидер терпит неудачу, алгоритм больше не будет прогрессировать - отсюда и требование завершения. Согласованность и целостность являются свойствами безопасности и составляют основу алгоритма консенсуса. Валидность охватывает тривиальное решение, при котором узлы всегда выбирают одно и то же заранее заданное значение и, таким образом, также достигают консенсуса по определению.

Существование решения, то есть реального алгоритма, для проблемы консенсуса, зависит от модели системы. Поэтому следует различать модель синхронной и асинхронной системы¹. Поскольку в большинстве случаев для отправки сообщений мы должны полагаться на общий канал связи, по крайней мере, связь является асинхронной, и, таким образом, наши приложения реального мира лучше подходят для этой модели. К сожалению, в такой среде есть доказательство невозможности Fischer et al. (1), известная как невозможность FLP, что показано в полностью асинхронной модели, даже если неисправен только один узел (даже не учитывая византийские сбои), не существует алгоритма, который всегда достигал бы консенсуса. Доказав, что во всех возможных алгоритмах существует выполнение, которое никогда не завершится, они показали, что ни один алгоритм не всегда достигает точки согласия.

Тем не менее реальные решения этой проблемы существуют. Обратите внимание, что результат невозможности применим к полностью асинхронным средам. Хотя наши приложения в реальном мире лучше подходят для этой модели, это не означает, что все условия точны (например, процессоры поддерживают внутренние часы). Использование менее строгих предположений относительно модели позволяет обойти результат невозможности FLP. Установка, например, верхней границы для доставки сообщений как ненадежного обнаружения сбоя может превратить канал связи в частичный синхронный. Системная модель, в которой проблема консенсуса разрешима. (2)

Алгоритмы, которые решают проблему консенсуса: Paxos, Raft, Viewstamped Replication, Zab

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