Консенсус в распределённых вычислениях

Консенсус в распределённых вычислениях — процесс согласования данных в распределённых вычислениях и многоагентных системах. Фундаментальной проблемой в распределённых вычислениях и многоагентных системах является достижение общей надёжности системы при наличии ряда ошибочных процессов. Это часто требует координации процессов или согласования некоторого значения данных, которое необходимо во время вычислений. Такой процесс принято называть достижением консенсуса.

Примеры достижения консенсуса включают согласование того, какие транзакции и в каком порядке следует фиксировать в базе данных, репликацию конечного автомата и атомарные широковещательные рассылки. Реальные приложения, часто требующие консенсуса, включают облачные вычисления, синхронизацию часов, PageRank, формирование мнений, интеллектуальные энергосистемы, оценку состояния, управление БПЛА или другими роботами, балансировку нагрузки, блокчейн и другие.

Описание проблемы

Достижение консенсуса требует соглашения между несколькими процессами (или агентами) для одного значения данных. Некоторые процессы (агенты) могут дать сбой или быть ненадёжными по другим причинам, поэтому протоколы консенсуса должны быть отказоустойчивыми или высоконадежными. Процессы должны каким-то образом выдвигать свои возможные значения, общаться друг с другом и согласовывать единое согласованное значение.

Проблема консенсуса является фундаментальной проблемой управления многоагентными системами. Один из подходов к достижению консенсуса заключается в том, чтобы все процессы (агенты) согласовали значение большинства. В этом контексте для большинства требуется как минимум на один больше половины доступных голосов (где каждому процессу даётся голос). Однако один или несколько ошибочных процессов могут исказить результирующий результат, так что консенсус может быть не достигнут или достигнут неправильно.

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

Прекращение (Termination)

В конце концов, каждый правильный процесс должен выдавать некоторое значение.

Целостность (Integrity)

Если все правильные процессы предлагают одно и то же значение $v$, то процесс поиска консенсуса также должен выдавать то же значение.

Согласие (Agreement)

Правильный процесс должен согласовывать одно и то же значение.

Протокол, гарантирующий консенсус среди n процессов, из которых не более t терпит неудачу, называется t-устойчивым.

При оценке производительности консенсусных протоколов интерес представляют два фактора: время работы и сложность сообщения. Время выполнения задаётся в нотации Big O в количестве раундов обмена сообщениями как функция некоторых входных параметров (обычно количества процессов и/или размера входного домена). Сложность сообщения относится к объёму трафика сообщений, который генерируется протоколом. Другие факторы могут включать использование памяти и размер сообщений.

Модели вычислений

Различные модели вычислений могут определять «проблему консенсуса». Некоторые модели могут иметь дело с полносвязными графами, тогда как другие — с кольцами и деревьями. В некоторых моделях разрешена идентификация сообщений, тогда как в других процессы полностью анонимны. Модели общей памяти, в которых процессы взаимодействуют, обращаясь к объектам в общей памяти, также являются важной областью исследований.

Каналы связи с прямой или переносимой идентификацией

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

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

Входы и выходы консенсуса

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

Частный случай проблемы консенсуса с одним значением, называемый бинарным консенсусом, ограничивает ввод и, следовательно, область вывода одной двоичной цифрой {0,1}. Хотя сами по себе бинарные протоколы консенсуса не очень полезны, они часто используются в качестве строительных блоков в более общих протоколах консенсуса, особенно для асинхронного консенсуса.

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

Аварийный сбой и византийские отказы

Существует два типа сбоев, с которыми может столкнуться процесс: аварийный отказ (англ. Crash failure) и т.н. «византийский отказ». В первом случае процесс внезапно останавливается и не возобновляется. Византийские отказы — это отказы, при которых не налагается никаких условий. Например, они могут возникать в результате действий злоумышленника. Процесс, в котором произошел византийский отказ, может отправлять другим процессам противоречивые данные или может заснуть, а затем возобновить работу после длительной задержки. Из этих двух типов отказов византийские отказы гораздо более разрушительны.

Таким образом, консенсусный протокол, допускающий византийские отказы, должен быть устойчивым ко всем возможным ошибкам.

Более сильная версия консенсуса, допускающая византийские отказы, даётся усилением ограничения целостности:

Целостность

Если правильный процесс выдаёт значение $v$, то это значение должно быть предложено каким-то правильным процессом.

Асинхронные и синхронные системы

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

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

Невозможность асинхронного детерминированного консенсуса

В полностью асинхронной распределённой системе с передачей сообщений, в которой по крайней мере один процесс может иметь аварийный сбой, в известной теореме 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, которые широко используются от компьютерных наук до теории управления.

Source	Synchrony	Authentication	Threshold	Rounds	Notes
Pease-Shostak-Lamport	Synchronous	Oral	$n>3f$	$f+1$	total communication $O(n^{f})$
Pease-Shostak-Lamport	Synchronous	Written	$n>f+1$	$f+1$	total communication $O(n^{f})$
Ben-Or	Asynchronous	Oral	$n>5f$	$O(2^{n})$ (expected)	expected $O(1)$ rounds when $f<{\sqrt {n}}$
Dolev et al.	Synchronous	Oral	$n>3f$	$2f+3$	total communication $O(f^{3}\log f)$
Dolev-Strong	Synchronous	Written	$n>f+1$	$f+1$	total communication $O(n^{2})$
Dolev-Strong	Synchronous	Written	$n>f+1$	$f+2$	total communication $O(nf)$
Feldman-Micali	Synchronous	Oral	$n>3f$	$O(1)$ (expected)
Katz-Koo	Synchronous	Written	$n>2f$	$O(1)$ (expected)	Requires PKI
PBFT	Asynchronous (safety)-- Synchronous (liveness)	Oral	$n>3f$
HoneyBadger	Asynchronous	Oral	$n>3f$	$O(\log n)$ (expected)	per tx communication $O(n)$ - requires public-key encryption
Abraham et al.	Synchronous	Written	$n>2f$	$8$
Byzantine Agreement Made Trivial	Synchronous	Signatures	$n>3f$	$9$ (expected)	Requires digital signatures

Биткойн использует доказательство работы, функцию регулировки сложности и функцию реорганизации для достижения консенсуса без разрешения в своей открытой одноранговой сети. Чтобы расширить блокчейн или распределённый реестр биткойна, майнеры пытаются решить криптографическую головоломку, где вероятность нахождения решения пропорциональна вычислительным усилиям, затрачиваемым на хеши в секунду. Узел, который первым решает такую головоломку, предлагает свою версию следующего блока транзакций, добавленную в реестр и в конечном итоге принятую всеми другими узлами. Поскольку любой узел в сети может попытаться решить проблему проверки работоспособности, атака Сивиллы в принципе невозможна, если только злоумышленник не владеет более 50% вычислительных ресурсов сети.

Другие криптовалюты (NEO, STRATIS и др.) используют доказательство доли, в котором узлы соревнуются за добавление блоков и зарабатывают соответствующие вознаграждения пропорционально доле или объему криптовалюты, выделенной, зарезервированной или находящейся во владении (staked) на некоторый момент времени. Одним из преимуществ «доказательства доли» перед системой «доказательства работы» является высокое потребление энергии, требуемое последней. Например, майнинг биткойнов, по оценкам 2018 года, потреблял энергию, сравнимую с потреблением таких стран как Чехия или Иордании.

Число консенсуса

Чтобы решить проблему консенсуса в системе с общей памятью, необходимо ввести параллельные объекты. Параллельный объект или общий объект — это структура данных, которая помогает параллельным процессам взаимодействовать для достижения соглашения. Традиционные реализации, использующие критические секции, сталкиваются с риском сбоя, если какой-либо процесс внутри критической секции прекращается или бездействует в течение слишком долгого времени. Исследователи определили свободу ожидания как гарантию того, что алгоритм завершится за конечное число шагов.

Число консенсуса параллельного объекта определяется как максимальное количество процессов в системе, которые могут достичь консенсуса данным объектом в реализации без ожидания. Объекты с консенсусным числом $n$ могут реализовать любой объект с консенсусным числом $n$ или ниже, но не могут реализовать какие-либо объекты с более высоким числом консенсуса. Консенсусные числа образуют то, что называется иерархией объектов синхронизации Херлихи.

Число консенсуса	Объекты
$1$	атомарные регистры чтения/записи, блокировки
$2$	test-and-set, swap, fetch-and-add, очередь без ожидания или стек
. . .	. . .
$2n-2$	назначение n-регистров
. . .	. . .
$\infty$	compare-and-swap, load-link/store-conditional, перемещение и обмен из памяти в память, очередь с операцией просмотра, fetch&cons, липкий байт

Согласно иерархии, регистры чтения/записи не могут обеспечить консенсус даже в системе с двумя процессами. Структуры данных, такие как стеки и очереди, могут обеспечить консенсус только между двумя процессами. Однако некоторые параллельные объекты являются универсальными (обозначены в таблице значком $\infty$ ), что означает, что они могут достичь консенсуса между любым количеством процессов и могут имитировать любые другие объекты с помощью последовательности операций.

Литература

• Артем Генкин, Алексей Михеев. Блокчейн для всех. Как работают криптовалюты, BaaS, NFT, DeFi и другие новые финансовые технологии. (рус.). — Альпина Паблишер, 2023. — 588 с. — ISBN 978-5-9614-8046-7..