Консенсус в распределённых вычислениях — процесс согласования данных в распределённых вычислениях и многоагентных системах. Фундаментальной проблемой в распределённых вычислениях и многоагентных системах является достижение общей надёжности системы при наличии ряда ошибочных процессов. Это часто требует координации процессов или согласования некоторого значения данных, которое необходимо во время вычислений. Такой процесс принято называть достижением консенсуса.
Примеры достижения консенсуса включают согласование того, какие транзакции и в каком порядке следует фиксировать в базе данных, репликацию конечного автомата и атомарные широковещательные рассылки. Реальные приложения, часто требующие консенсуса, включают облачные вычисления, синхронизацию часов, PageRank, формирование мнений, интеллектуальные энергосистемы, оценку состояния, управление БПЛА или другими роботами, балансировку нагрузки, блокчейн и другие.
Описание проблемы Достижение консенсуса требует соглашения между несколькими процессами (или агентами) для одного значения данных. Некоторые процессы (агенты) могут дать сбой или быть ненадёжными по другим причинам, поэтому протоколы консенсуса должны быть отказоустойчивыми или высоконадежными. Процессы должны каким-то образом выдвигать свои возможные значения, общаться друг с другом и согласовывать единое согласованное значение.
Проблема консенсуса является фундаментальной проблемой управления многоагентными системами. Один из подходов к достижению консенсуса заключается в том, чтобы все процессы (агенты) согласовали значение большинства. В этом контексте для большинства требуется как минимум на один больше половины доступных голосов (где каждому процессу даётся голос). Однако один или несколько ошибочных процессов могут исказить результирующий результат, так что консенсус может быть не достигнут или достигнут неправильно.
Протоколы, решающие проблемы консенсуса, предназначены для работы с ограниченным числом ошибочных процессов. Эти протоколы должны удовлетворять ряду требований. Протокол поиска консенсуса, допускающий отказы при остановке, должен удовлетворять следующим требованиям:
Прекращение (Termination) В конце концов, каждый правильный процесс должен выдавать некоторое значение. Целостность (Integrity) Если все правильные процессы предлагают одно и то же значение , то процесс поиска консенсуса также должен выдавать то же значение. Согласие (Agreement) Правильный процесс должен согласовывать одно и то же значение.
Протокол, гарантирующий консенсус среди n процессов, из которых не более t терпит неудачу, называется t-устойчивым.
При оценке производительности консенсусных протоколов интерес представляют два фактора: время работы и сложность сообщения. Время выполнения задаётся в нотации Big O в количестве раундов обмена сообщениями как функция некоторых входных параметров (обычно количества процессов и/или размера входного домена). Сложность сообщения относится к объёму трафика сообщений, который генерируется протоколом. Другие факторы могут включать использование памяти и размер сообщений.
Модели вычислений Различные модели вычислений могут определять «проблему консенсуса». Некоторые модели могут иметь дело с полносвязными графами, тогда как другие — с кольцами и деревьями. В некоторых моделях разрешена идентификация сообщений, тогда как в других процессы полностью анонимны. Модели общей памяти, в которых процессы взаимодействуют, обращаясь к объектам в общей памяти, также являются важной областью исследований.
Каналы связи с прямой или переносимой идентификацией В большинстве моделей протокола связи участники общаются через идентифицированные каналы. Это означает, что сообщения не являются анонимными, и получатели знают источник каждого сообщения. Некоторые модели предполагают более сильную, переносимую форму идентификации, при которой каждое сообщение подписывается отправителем, так что получатель знает не только непосредственный источник каждого сообщения, но и участника, который его создал. Этот более строгий тип идентификации достигается с помощью цифровых подписей; при такой идентификации протоколы могут допускать большее количество ошибок.
Две разные модели идентификации часто называют моделями устного общения и письменного общения . В модели устного общения известен непосредственный источник информации, тогда как в более сильных моделях письменного общения получатель на каждом этапе узнает не только непосредственный источник сообщения, но и историю передачи сообщения.
Входы и выходы консенсуса В наиболее традиционных протоколах консенсуса с одним значением, таких как Paxos, сотрудничающие узлы согласовывают одно значение, такое как целое число, которое может иметь переменный размер, чтобы кодировать полезные метаданные, такие как транзакция, зафиксированная в базе данных.
Частный случай проблемы консенсуса с одним значением, называемый бинарным консенсусом, ограничивает ввод и, следовательно, область вывода одной двоичной цифрой {0,1}. Хотя сами по себе бинарные протоколы консенсуса не очень полезны, они часто используются в качестве строительных блоков в более общих протоколах консенсуса, особенно для асинхронного консенсуса.
В многозначных согласованных протоколах, таких как Multi-Paxos и Raft, цель состоит в том, чтобы согласовать не просто одно значение, а ряд значений с течением времени, формируя постепенно растущую историю. В то время как многозначный консенсус может быть достигнут путем последовательного запуска нескольких итераций однозначного консенсусного протокола, многие оптимизации и другие соображения, такие как поддержка реконфигурации, могут сделать многозначные консенсусные протоколы более эффективными на практике.
Аварийный сбой и византийские отказы Существует два типа сбоев, с которыми может столкнуться процесс: аварийный отказ () и т.н. «византийский отказ». В первом случае процесс внезапно останавливается и не возобновляется. Византийские отказы — это отказы, при которых не налагается никаких условий. Например, они могут возникать в результате действий злоумышленника. Процесс, в котором произошел византийский отказ, может отправлять другим процессам противоречивые данные или может заснуть, а затем возобновить работу после длительной задержки. Из этих двух типов отказов византийские отказы гораздо более разрушительны.
Таким образом, консенсусный протокол, допускающий византийские отказы, должен быть устойчивым ко всем возможным ошибкам.
Более сильная версия консенсуса, допускающая византийские отказы, даётся усилением ограничения целостности:
Целостность Если правильный процесс выдаёт значение , то это значение должно быть предложено каким-то правильным процессом.
Асинхронные и синхронные системы Проблема консенсуса может рассматриваться в как для синхронных, так и асинхронных систем. Хотя в реальном мире зачастую процессы по своей природе асинхронны, более практично и часто проще моделировать синхронные системы.
В синхронных системах предполагается, что все коммуникации осуществляются циклами . В одном раунде процесс может отправить все необходимые ему сообщения, получая при этом все сообщения от других процессов. Таким образом, ни одно сообщение из одного раунда не может влиять на сообщения, отправленные в этом же раунде.
Невозможность асинхронного детерминированного консенсуса В полностью асинхронной распределённой системе с передачей сообщений, в которой по крайней мере один процесс может иметь аварийный сбой, в известной теореме FLP (Fischer, Lynch, and Paterson) было доказано, что детерминированный алгоритм для достижения консенсуса невозможен. Этот невозможный результат вытекает из сценариев планирования наихудшего случая, которые вряд ли произойдут на практике, за исключением враждебных ситуаций, таких атака злоумышленник, атакующий. В большинстве обычных ситуаций планирование процессов имеет определённую степень естественной случайности.
В асинхронной модели некоторые формы сбоев могут обрабатываться синхронным согласованным протоколом. Например, потеря канала связи может быть смоделирована как процесс, в котором произошёл византийский сбой.
Алгоритмы рандомизированного консенсуса могут обойти результат невозможности FLP, достигнув как безопасности, так и живучести с огромной вероятностью, даже при наихудших сценариях планирования, таких как интеллектуальный злоумышленник в сети.
Разрешённый и неразрешённый консенсус Алгоритмы консенсуса традиционно предполагают, что набор участвующих узлов фиксирован и задан с самого начала: то есть, что какой-то предварительный (ручной или автоматический) процесс настройки определил известную группу участников, которые могут идентифицировать друг друга как членов группы. В отсутствие такой чётко определённой закрытой группы атака Сивиллы на группу с открытым консенсусом может обойти даже византийский алгоритм консенсуса, просто создав достаточно виртуальных участников, чтобы преодолеть порог отказоустойчивости.
Протокол консенсуса без определения группы, напротив, позволяет любому в сети динамически присоединяться и участвовать без предварительного разрешения, но вместо этого налагает форму искусственной стоимости или барьера для входа, чтобы уменьшить угрозу атаки Сивиллы. Биткойн представил первый протокол консенсуса без разрешений, использующий доказательство работы и функцию корректировки сложности, в которой участники соревнуются в решении криптографических хэш-головоломок и вероятностно зарабатывают право на фиксацию блоков и получают соответствующие вознаграждения пропорционально их вложенным вычислительным усилиям. Частично мотивированные высокими затратами энергии на этот подход, последующие протоколы консенсуса без разрешений предложили или приняли другие правила участия для защиты от атак Сивиллы, такие как доказательство доли, доказательство пространства и доказательство полномочий.
Примеры протоколов консенсуса В распределённых и облачных вычислительных системах широко используется алгоритм консенсуса Paxos Лесли Лэмпорта и его варианты, такие как Raft. Эти алгоритмы, как правило, синхронны, зависят от избранного лидера для достижения прогресса и допускают отказы (crashes), но не византийские сбои (Byzantine failures).
Примером бинарного протокола консенсуса с полиномиальным временем, допускающего византийские сбои, является алгоритм Phase King Гарая и Бермана. Алгоритм достигает консенсуса в модели синхронной передачи сообщений с n процессами и f сбоями при условии n > 4 f .
Google реализовал распределенную библиотеку сервиса блокировки под названием Chubby. Chubby хранит информацию о блокировках в небольших файлах, которые, в свою очередь, хранятся в реплицированной базе данных, что обеспечивает восстановление в случае сбоев. База данных реализована на основе отказоустойчивого уровня журнала, основанного на алгоритме консенсуса Paxos . В этой схеме клиенты Chubby взаимодействуют с мастером Paxos для доступа/обновления реплицированного журнала.
Другой хорошо известный подход называется алгоритмами типа MSR, которые широко используются от компьютерных наук до теории управления. SourceSynchronyAuthenticationThresholdRoundsNotesPease-Shostak-Lamport SynchronousOraltotal communication Pease-Shostak-Lamport SynchronousWrittentotal communication Ben-Or AsynchronousOral (expected)expected rounds when Dolev et al.SynchronousOraltotal communication Dolev-Strong SynchronousWrittentotal communication Dolev-Strong SynchronousWrittentotal communication Feldman-Micali SynchronousOral (expected)Katz-Koo SynchronousWritten (expected)Requires PKIPBFT Asynchronous (safety)-- Synchronous (liveness)OralHoneyBadger AsynchronousOral (expected)per tx communication - requires public-key encryptionAbraham et al.SynchronousWrittenByzantine Agreement Made Trivial SynchronousSignatures (expected)Requires digital signatures