Консенсус (информатика) - Consensus (computer science)

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

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

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

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

Протоколы, которые решают проблемы консенсуса, предназначены для работы с ограниченным количеством неисправных процессы. Чтобы эти протоколы были полезными, они должны удовлетворять ряду требований. Например, в тривиальном протоколе все процессы могут выводить двоичное значение 1. Это бесполезно, и поэтому требование изменяется таким образом, что вывод должен каким-то образом зависеть от ввода. То есть выходное значение протокола консенсуса должно быть входным значением некоторого процесса. Другое требование состоит в том, что процесс может принять решение о выходном значении только один раз, и это решение не может быть отменено. Процесс называется правильным при выполнении, если он не дает сбоев. Протокол консенсуса, допускающий сбои при остановке, должен удовлетворять следующим свойствам.^[1]

Прекращение

В конце концов, каждый правильный процесс определяет какую-то ценность.

Честность

Если все правильные процессы предложили одно и то же значение ${displaystyle v}$, то любой правильный процесс должен решить ${displaystyle v}$.

Соглашение

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

Варианты определения честность может быть подходящим в зависимости от приложения. Например, более слабым типом целостности будет значение решения, равное значению, предложенному некоторым правильным процессом, а не обязательно всем.^[1] В Честность состояние также известно как срок действия в литературе.^[1]

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

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

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

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

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

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

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

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

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

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

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

Катастрофа и византийские неудачи

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

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

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

Честность

Если правильный процесс решит ${displaystyle v}$, тогда ${displaystyle v}$ должно быть, было предложено каким-то правильным процессом.

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

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

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

Результат невозможности FLP для асинхронного детерминированного консенсуса

В полностью асинхронной распределенной системе передачи сообщений, в которой хотя бы один процесс может иметь авария, это было доказано в знаменитых Результат невозможности ФЛП который детерминированный алгоритм для достижения консенсуса невозможно.^[5] Такой результат невозможности проистекает из наихудших сценариев планирования, которые маловероятны на практике, за исключением враждебных ситуаций, таких как интеллектуальный злоумышленник с отказом в обслуживании в сети. В большинстве обычных ситуаций планирование процессов имеет степень естественной случайности.^[4]

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

Рандомизированный Алгоритмы консенсуса могут обойти результат невозможности FLP за счет обеспечения как безопасности, так и живучести с подавляющей вероятностью, даже при наихудших сценариях планирования, таких как интеллектуальный злоумышленник с отказом в обслуживании в сети.^[6]

Разрешенный консенсус против несанкционированного

Алгоритмы консенсуса традиционно предполагают, что набор узлов-участников фиксирован и задан с самого начала: то есть, что некоторый предварительный (ручной или автоматический) процесс настройки имеет разрешенный конкретная известная группа участников, которые могут аутентифицировать друг друга как члены группы. В отсутствие такой четко определенной закрытой группы с аутентифицированными членами Атака Сибиллы против группы открытого консенсуса может победить даже византийский алгоритм консенсуса, просто создав достаточное количество виртуальных участников, чтобы преодолеть порог отказоустойчивости.

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

Эквивалентность проблем согласования

Представляют интерес три проблемы согласования.

Прекращение надежной трансляции

Коллекция ${displaystyle n}$ процессы, пронумерованные от ${displaystyle 0}$ к ${displaystyle n-1,}$ общаться, отправляя сообщения друг другу. Процесс ${displaystyle 0}$ должен передавать значение ${displaystyle v}$ ко всем процессам, таким как:

1. если процесс ${displaystyle 0}$ правильно, то каждый правильный процесс получает ${displaystyle v}$
2. для любых двух правильных процессов каждый процесс получает одно и то же значение.

Он также известен как проблема генерала.

Консенсус

Формальные требования к протоколу консенсуса могут включать:

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

Слабая интерактивная согласованность

За п процессов в частично синхронной системе (система чередует хорошие и плохие периоды синхронизации), каждый процесс выбирает частное значение. Процессы взаимодействуют друг с другом раундами для определения общедоступной ценности и генерации вектора консенсуса со следующими требованиями:^[7]

1. если правильный процесс отправляет ${displaystyle v}$, то все правильные процессы получают либо ${displaystyle v}$ или ничего (свойство целостности)
2. все сообщения, отправленные в раунде правильным процессом, принимаются в одном раунде всеми правильными процессами (свойство согласованности).

Можно показать, что варианты этих проблем эквивалентны в том смысле, что решение проблемы в модели одного типа может быть решением другой проблемы в модели другого типа. Например, решение проблемы Weak Byzantine General в модели передачи сообщений с синхронной аутентификацией приводит к решению проблемы Weak Interactive Consistency.^[8] Алгоритм интерактивной согласованности может решить проблему консенсуса, если каждый процесс выбирает значение большинства в своем векторе консенсуса в качестве своего согласованного значения.^[9]

Результаты разрешимости некоторых проблем согласования

Существует t-устойчивый анонимный синхронный протокол, который решает Проблема византийских генералов,^[10][11] если ${displaystyle {frac {t} {n}} <{frac {1} {3}}}$ и дело Слабых Византийских Генералов^[8] куда ${displaystyle t}$ это количество отказов и ${displaystyle n}$ количество процессов.

Для систем с ${displaystyle n}$ процессоры, из которых ${displaystyle f}$ являются византийскими, было показано, что не существует алгоритма, который решает проблему консенсуса для ${displaystyle nleq 3f}$ в модель устных сообщений.^[12] Доказательство строится, сначала показывая невозможность для случая трех узлов ${displaystyle n = 3}$ и используя этот результат, чтобы спорить о разделах процессоров. в модель письменных сообщений есть протоколы, которые могут терпеть ${displaystyle n = f + 1}$.^[2]

В полностью асинхронной системе нет консенсусного решения, которое могло бы выдержать один или несколько аварийных отказов, даже когда требуется только свойство нетривиальности.^[5] Этот результат иногда называют доказательством невозможности ФЛП по имени авторов. Майкл Дж. Фишер, Нэнси Линч, и Майк Патерсон кто был награжден Премия Дейкстры за эту значительную работу. Результат FLP был механически подтвержден на предмет соответствия даже при предположения о справедливости.^[13] Тем не менее, FLP не утверждает, что консенсус никогда не может быть достигнут: просто, согласно предположениям модели, ни один алгоритм не может всегда достичь консенсуса за ограниченное время. На практике это маловероятно.

Некоторые протоколы консенсуса

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

Примером протокола бинарного консенсуса с полиномиальным временем, допускающего византийские сбои, является алгоритм Phase King.^[14] Гарая и Бермана. Алгоритм решает консенсус в модели синхронной передачи сообщений с п процессы и до ж отказы, при условии п > 4ж.В алгоритме царя фаз есть ж + 1 фаз, по 2 цикла на фазу. Каждый процесс отслеживает свой предпочтительный выход (изначально равный собственному входному значению процесса). В первом раунде каждой фазы каждый процесс передает свое предпочтительное значение всем другим процессам. Затем он получает значения от всех процессов и определяет, какое значение является основным значением, и его количество. Во втором раунде фазы процесс, идентификатор которого совпадает с номером текущей фазы, назначается королем фазы. Король транслирует значение большинства, которое он наблюдал в первом раунде, и служит решающим фактором. Затем каждый процесс обновляет свое предпочтительное значение следующим образом. Если подсчет большинства значений, процесс, наблюдаемый в первом раунде, больше, чем п/2 + ж, процесс меняет свое предпочтение на это значение большинства; в противном случае используется значение царя фазы. В конце ж + 1 фазы процессы выводят свои предпочтительные значения.

Google внедрил распределенная служба блокировки библиотека называется Круглолицый.^[15] Chubby хранит информацию о блокировках в небольших файлах, которые хранятся в реплицируемой базе данных, чтобы обеспечить высокую доступность в случае сбоев. База данных реализована поверх уровня отказоустойчивого журнала, основанного на Алгоритм консенсуса Paxos. В этой схеме клиенты Chubby общаются с Paxos. владелец для доступа / обновления реплицированного журнала; т.е. чтение / запись в файлы.^[16]

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

Другой хорошо известный подход, называемый алгоритмами типа MSR, широко используется от информатики до теории управления.^[17][18][19]

Источник	Синхронность	Аутентификация	Порог	Раундов	Примечания
Пиз-Шостак-Лампорт [10]	Синхронный	Устный	${displaystyle n> 3f}$	${displaystyle f + 1}$	полное общение ${displaystyle O (n ^ {f})}$
Пиз-Шостак-Лампорт [10]	Синхронный	Написано	${displaystyle n> f + 1}$	${displaystyle f + 1}$	полное общение ${displaystyle O (n ^ {f})}$
Бен-Ор [20]	Асинхронный	Устный	${displaystyle n> 5f}$	${displaystyle O (2 ^ {n})}$ (ожидал)	ожидал ${displaystyle O (1)}$ раундов, когда ${displaystyle f <{sqrt {n}}}$
Dolev et al. [21]	Синхронный	Устный	${displaystyle n> 3f}$	${displaystyle 2f + 3}$	полное общение ${displaystyle O (f ^ {3} log f)}$
Долев-Стронг [2]	Синхронный	Написано	${displaystyle n> f + 1}$	${displaystyle f + 1}$	полное общение ${displaystyle O (n ^ {2})}$
Долев-Стронг [2]	Синхронный	Написано	${displaystyle n> f + 1}$	${displaystyle f + 2}$	полное общение ${displaystyle O (nf)}$
Фельдман-Микали [22]	Синхронный	Устный	${displaystyle n> 3f}$	${displaystyle O (1)}$ (ожидал)
Кац-Ку [23]	Синхронный	Написано	${displaystyle n> 2f}$	${displaystyle O (1)}$ (ожидал)	Требуется PKI
PBFT [24]	Асинхронный (безопасность) - Синхронный (живучесть)	Устный	${displaystyle n> 3f}$
HoneyBadger [25]	Асинхронный	Устный	${displaystyle n> 3f}$	${displaystyle O (log n)}$ (ожидал)	за tx-связь ${displaystyle O (n)}$ - требует шифрования с открытым ключом
Abraham et al. [26]	Синхронный	Написано	${displaystyle n> 2f}$	${displaystyle 8}$
Византийское соглашение стало тривиальным [27] [28]	Синхронный	Подписи	${displaystyle n> 3f}$	${displaystyle 9}$ (ожидал)	Требуется цифровая подпись

Протоколы консенсуса без разрешения

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

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

Некоторые криптовалюты, такие как Ripple, используют систему проверки узлов для проверки реестра. Эта система, используемая Ripple, называемая алгоритмом консенсуса протокола Ripple (RPCA), работает поэтапно: Шаг 1: каждый сервер составляет список допустимых транзакций-кандидатов; Шаг 2: каждый сервер объединяет всех кандидатов из своего списка уникальных узлов (UNL) и голосует за их достоверность; Шаг 3: транзакции, превышающие минимальный порог, переходят в следующий раунд; Шаг 4: финальный раунд требует 80% согласия^[30]

Другие правила участия, используемые в протоколах консенсуса без разрешения для навязывания барьеры для входа и сопротивляться атаки Сибиллы включают доказательство полномочий, доказательство места, доказательство ожога или доказательство истекшего времени. Эти альтернативы снова в значительной степени мотивированы большим количеством вычислительной энергии, потребляемой доказательством работы.^[31] Доказательство емкости используется криптовалютой, такой как Burstcoin.

В отличие от приведенных выше правил неограниченного участия, каждый из которых вознаграждает участников пропорционально сумме инвестиций в какое-либо действие или ресурс, доказательство личности Протоколы стремятся предоставить каждому реальному участнику-человеку ровно одну единицу права голоса при неразрешенном консенсусе, независимо от экономических вложений.^[32][33] Предлагаемые подходы к достижению индивидуального распределения силы консенсуса для доказательства личности включают физические псевдонимы сторон,^[34] социальные сети,^[35] псевдонимы, выданные государством,^[36] и биометрия.^[37]

Протоколы консенсуса с общей памятью

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

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

Другая реализация параллельного объекта называется реализацией без ожидания, которая может гарантировать консенсус за конечное число шагов. Достаточно ли мощный объект данного типа для решения проблем консенсуса? Морис Херлихи дал «Иерархию невозможности и универсальности».^[38]

Номер консенсуса	Объекты
${displaystyle 1}$	Регистры чтения / записи
${displaystyle 2}$	тест и установка, замена, выборка и добавление, очередь, стек
...	...
${displaystyle 2n-2}$	присвоение n-регистров
...	...
${displaystyle infty}$	Перемещение и подкачка из памяти в память, расширенная очередь, сравнение и замена, выборка и минусы, липкий байт

Число консенсуса в иерархии означает максимальное количество процессов в системе, которые могут достичь консенсуса по данному объекту. Объекты с более высоким числом консенсуса не могут быть реализованы объектами с более низким числом консенсуса.

Согласно иерархии, регистры чтения / записи не могут достичь консенсуса даже в двухпроцессной системе. Структура данных, такая как стек, очередь и т. Д., Может обеспечить консенсус между двумя процессами. Почему эти объекты не могут достичь консенсуса между большим количеством процессов? Эффективный способ доказать это - воспользоваться преимуществом двойственности. Предположим, что выход является двоичным, состояние является бивалентным, если возможны оба из двух выходов, и если выход, достижимый из состояния, равен только 0/1, состояние называется 0-валентным / 1-валентным. Основная идея состоит в том, чтобы создать противоречие, выполнив некоторые операции для получения состояния, которое одновременно является 0-валентным и 1-валентным.

Однако некоторые параллельные объекты универсальны, что означает, что они могут достигать консенсуса между любым количеством процессов и могут имитировать любые другие объекты. Способ моделирования других объектов с помощью универсальных объектов состоит в построении последовательности операций с этим параллельным объектом.^[38]

Смотрите также

• Единый консенсус
• Квантовое византийское соглашение
• Византийская отказоустойчивость

Рекомендации

дальнейшее чтение

• Herlihy, M .; Шавит, Н. (1999). «Топологическая структура асинхронной вычислимости». Журнал ACM. 46 (6): 858. CiteSeerX  10.1.1.78.1455. Дои:10.1145/331524.331529. S2CID  5797174.
• Сакс, М .; Захароглов, Ф. (2000). «Соглашение о k-множестве без ожидания невозможно: топология общедоступных знаний». SIAM Журнал по вычислениям. 29 (5): 1449–1483. Дои:10.1137 / S0097539796307698.