Consensus (computer science)

Введение

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

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

Проблема консенсуса требует согласия между рядом процессов (или агентов) по одному значению данных. Некоторые из процессов (агентов) могут потерпеть неудачу или быть ненадежными в других отношениях, поэтому протоколы консенсуса должны быть устойчивы к ошибкам или устойчивы к импульсу. Процессы должны выдвигать свои ценности-кандидаты, общаться друг с другом и согласовывать единую ценность консенсуса. Проблема консенсуса является основополагающей проблемой в управлении многоагентными системами. Один из подходов к формированию консенсуса заключается в том, чтобы все процессы (агенты) согласовали большинство. В этом контексте большинство требует, по крайней мере, более половины имеющихся голосов (где каждый процесс дается один голос). Однако один или несколько неисправных процессов могут исказить полученный результат таким образом, что консенсус может быть не достигнут или может быть достигнут неправильно. Протоколы, которые решают проблемы консенсуса, предназначены для решения ограниченного числа неисправных процессов. Эти протоколы должны удовлетворять нескольким требованиям, чтобы быть полезными. Например, тривиальный протокол может иметь все процессы вывода бинарного значения 1. Это не полезно, поэтому требование изменяется таким образом, что производство должно зависеть от входных ресурсов. То есть, выходное значение консенсусного протокола должно быть входным значением какого-либо процесса. Еще одно требование заключается в том, что процесс может принять решение о выходном значении только один раз, и это решение является необратимым. Метод является правильным в исполнении, если он не испытывает сбоев. Консенсусный протокол, допускающий сбои в остановке, должен удовлетворять следующим свойствам[1]. В конце концов, каждый правильный процесс решает некоторую ценность. Целостность Если все правильные процессы предлагают одно и то же значение, то любой правильный процесс должен решить Согласие Каждый правильный процесс должен согласиться на одно и то же значение. В зависимости от применения могут быть целесообразны изменения в определении целостности. Например, более слабый тип целостности будет для значения решения равен значению, которое предложен некоторым правильным процессом, но не обязательно всем из них. Две различные модели аутентификации часто называют моделями устной и письменной коммуникации. В модели устной коммуникации непосредственный источник информации известен, тогда как в более сильных, письменных моделях коммуникации, каждый шаг на пути получателя узнает не только непосредственный источник сообщения, но и историю сообщения.

The consensus problem requires agreement among a number of processes (or agents) on a single data value. Some of the processes (agents) may fail or be unreliable in other ways, so consensus protocols must be fault tolerant or resilient. The processes must put forth their candidate values, communicate with one another, and agree on a single consensus value. The consensus problem is a fundamental problem in controlling multi agent systems. One approach to generating consensus is for all processes (agents) to agree on a majority value. In this context, a majority requires at least one more than half of the available votes (where each process is given a vote). However, one or more faulty processes may skew the resultant outcome such that consensus may not be reached or may be reached incorrectly. Protocols that solve consensus problems are designed to deal with a limited number of faulty processes. These protocols must satisfy several requirements to be useful. For instance, a trivial protocol could have all processes output binary value 1. This is not useful; thus, the requirement is modified such that the production must depend on the input. That is, the output value of a consensus protocol must be the input value of some process. Another requirement is that a process may decide upon an output value only once, and this decision is irrevocable. A method is correct in an execution if it does not experience a failure. A consensus protocol tolerating halting failures must satisfy the following properties.[1]. Termination Eventually, every correct process decides some value. Integrity If all the correct processes proposed the same value , then any correct process must decide Agreement Every correct process must agree on the same value. Variations on the definition of integrity may be appropriate, according to the application. For example, a weaker type of integrity would be for the decision value to equal a value that some correct process proposed – not necessarily all of them. The two different authentication models are often called oral communication and written communication models. In an oral communication model, the immediate source of information is known, whereas in stronger, written communication models, every step along the receiver learns not just the immediate source of the message, but the communication history of the message.

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

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

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

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

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

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

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

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

Проблемы эквивалентности соглашений

Три проблемы соглашения, представляющие интерес, следующие.

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

Существует t устойчивый анонимный синхронный протокол, который решает проблему византийских генералов, если и случай слабых византийских генералов Доказательство построено, сначала показав невозможность для случая с тремя узлами и используя этот результат, чтобы спорить о разделах процессоров. В модели письменных сообщений есть протоколы, которые могут терпеть Однако, FLP не утверждает, что консенсус никогда не может быть достигнут: просто, что в соответствии с предположениями модели, ни один алгоритм не может всегда достичь консенсуса в ограниченное время. На практике это маловероятно.

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

Алгоритм консенсуса Paxos Лесли Лэмпорт и его варианты, такие как Raft, широко используются в широко распространенных распределенных и облачных вычислительных системах. Эти алгоритмы, как правило, синхронны, зависят от избранного лидера, чтобы добиться прогресса, и терпят только сбои, а не византийские неудачи. Примером протокола двоичного консенсуса в полиномиальном времени, который терпит византийские сбои, является алгоритм Phase King Гарея и Бермана. Алгоритм решает консенсус в модели синхронного передачи сообщений с n процессами и до f неудач при условии, что n > 4f. В алгоритме фазового короля существуют фазы f + 1, с 2 раундами на фазу. Каждый процесс отслеживает свой предпочтительный выход (первоначально равен собственному входному значению процесса). В первом раунде каждой фазы каждый процесс передает свои предпочтительные значения всем другим процессам. Затем он получает значения от всех процессов и определяет, какое значение является большинством и его количество. Во втором раунде фазы процесс, идентификатор которого соответствует текущему номеру фазы, обозначается королем фазы. Король передает значение большинства, которое он наблюдал в первом раунде, и служит решающим фактором. Каждый процесс затем обновляет свое предпочтительное значение следующим образом. Если число большинства, наблюдаемое в первом раунде, больше n/2 + f, процесс меняет свое предпочтение на это значение большинства; в противном случае он использует значение короля фазы. В конце фазы f + 1 процессы выводят свои предпочтительные значения. Google внедрил распределенную библиотеку служб блокировки под названием Chubby. Chubby сохраняет информацию о замке в небольших файлах, которые хранятся в реплицированной базе данных для обеспечения высокой доступности в случае сбоев. База данных реализована на вершине лог-слоя, терпимого к ошибкам, который основан на алгоритме консенсуса Paxos. В этой схеме клиенты Chubby общаются с мастером Paxos для доступа к реплицированному журналу; то есть, читают/записывают в файлы. Многие онлайн-игры стратегии в режиме реального времени с одноранговым взаимодействием используют модифицированный протокол lockstep в качестве консенсусного протокола для управления игровым состоянием между игроками в игре. Каждое игровое действие приводит к передаче дельты состояния игры всем другим игрокам в игре вместе с хэшем общего состояния игры. Каждый игрок проверяет изменение, применяя дельту к своему собственному состоянию игры и сравнивая хэши состояния игры. Если хэши не согласны, то голосование проводится, и те игроки, чье игровое состояние находится в меньшинстве, отключаются и удаляются из игры (известный как десинхронность). Другой хорошо известный подход называется алгоритмы типа MSR, которые широко используются в компьютерной науке для теории управления. Источник Синхронный порог аутентификации Округи Примечания Pease Shostak Lamport Асинхронный Оральный (ожидаемый) Ожидаемые раунды, когда Dolev et al. Синхронная устная общая коммуникация Долев Сильная синхронная устная (ожидается) Кац Ку Синхронная письменная (ожидается) Требует инфраструктуры общедоступного ключа (PKI) PBFT Асинхронная (безопасность) Синхронная (жизненность) устная Медовый Беджер Асинхронная устная (ожидается) по tx коммуникация требует шифрования с общедоступным ключом Abraham et al. Синхронное письменное византийское соглашение сделано тривиальным Синхронные подписи (ожидается) Требует цифровых подписей

The Paxos consensus algorithm by Leslie Lamport, and variants of it such as Raft, are used pervasively in widely deployed distributed and cloud computing systems. These algorithms are typically synchronous, dependent on an elected leader to make progress, and tolerate only crashes and not Byzantine failures. An example of a polynomial time binary consensus protocol that tolerates Byzantine failures is the Phase King algorithm by Garay and Berman. The algorithm solves consensus in a synchronous message passing model with n processes and up to f failures, provided n > 4f. In the phase king algorithm, there are f + 1 phases, with 2 rounds per phase. Each process keeps track of its preferred output (initially equal to the process's own input value). In the first round of each phase each process broadcasts its own preferred value to all other processes. It then receives the values from all processes and determines which value is the majority value and its count. In the second round of the phase, the process whose id matches the current phase number is designated the king of the phase. The king broadcasts the majority value it observed in the first round and serves as a tie breaker. Each process then updates its preferred value as follows. If the count of the majority value the process observed in the first round is greater than n/2 + f, the process changes its preference to that majority value; otherwise it uses the phase king's value. At the end of f + 1 phases the processes output their preferred values. Google has implemented a distributed lock service library called Chubby. Chubby maintains lock information in small files which are stored in a replicated database to achieve high availability in the face of failures. The database is implemented on top of a fault tolerant log layer which is based on the Paxos consensus algorithm. In this scheme, Chubby clients communicate with the Paxos master in order to access/update the replicated log; i. e., read/write to the files. Many peer to peer online real time strategy games use a modified lockstep protocol as a consensus protocol in order to manage game state between players in a game. Each game action results in a game state delta broadcast to all other players in the game along with a hash of the total game state. Each player validates the change by applying the delta to their own game state and comparing the game state hashes. If the hashes do not agree then a vote is cast, and those players whose game state is in the minority are disconnected and removed from the game (known as a desync.) Another well known approach is called MSR type algorithms which have been used widely from computer science to control theory. Source Synchrony Authentication Threshold Rounds Notes Pease Shostak Lamport Asynchronous Oral (expected) expected rounds when Dolev et al. Synchronous Oral total communication Dolev Strong Synchronous Oral (expected) Katz Koo Synchronous Written (expected) Requires Public Key Infrastructure (PKI) PBFT Asynchronous (safety)Synchronous (liveness) Oral HoneyBadger Asynchronous Oral (expected) per tx communication requires public key encryption Abraham et al. Synchronous Written Byzantine Agreement Made Trivial Synchronous Signatures (expected) Requires digital signatures

Номер консенсуса

Для решения проблемы консенсуса в системе общей памяти должны быть введены одновременные объекты. Одновременный объект, или общий объект, представляет собой структуру данных, которая помогает одновременным процессам общаться, чтобы достичь соглашения. Традиционные реализации, использующие критические секции, рискуют потерпеть крах, если какой-то процесс умирает внутри критической секции или спит на неодобрительно длительное время. Исследователи определили свободу ожидания как гарантию того, что алгоритм завершит в конечном числе шагов. Консенсусный номер одновременного объекта определяется как максимальное количество процессов в системе, которые могут достичь консенсуса данным объектом в реализации без ожидания. Объекты с консенсусом числа могут реализовать любой объект с консенсусом числа или ниже, но не может реализовать любые объекты с более высоким консенсусом числа. Консенсусные числа образуют так называемую иерархию объектов синхронизации Герлихи. Объекты консенсусного числа атомные регистры чтения/записи, тест и набор мутекс, обмен, извлечение и добавление, ожидание свободной очереди или стека n присвоение регистра сравнение и обмен, загрузка ссылки/хранилища условно, перемещение памяти в память и обмен, очередь с операцией peek, fetch&cons, липкий байт Согласно иерархии, регистры чтения/записи не могут решить консенсус даже в системе 2 процесса. Структуры данных, такие как стеки и очереди, могут решать только консенсус между двумя процессами. Однако некоторые одновременные объекты являются универсальными (отмечены в таблице с), что означает, что они могут разрешать консенсус среди любого количества процессов и имитировать любые другие объекты через последовательность операций.