Консенсус (компьютерные науки)

Концепция в информатике

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

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

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

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

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

Прекращение

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

Честность

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

Соглашение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Честность

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

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

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

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

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

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

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

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

Разрешенный и неразрешенный консенсус

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

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

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

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

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

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

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

Ее также называют «Проблемой генерала».

Консенсус

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Некоторые криптовалюты, такие как Ripple, используют систему валидации узлов для валидации реестра. Эта система, используемая Ripple, называется Ripple Protocol Consensus Algorithm (RPCA), и работает раундами:

Шаг 1: каждый сервер составляет список допустимых транзакций-кандидатов;

Шаг 2: каждый сервер объединяет всех кандидатов из своего списка уникальных узлов (UNL) и голосует за их достоверность;

Шаг 3: транзакции, преодолевшие минимальный порог, переходят в следующий раунд;

Шаг 4: для финального раунда требуется 80% согласия. ^[32]

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

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

Консенсусное число

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

Число консенсуса параллельного объекта определяется как максимальное число процессов в системе, которые могут достичь консенсуса данным объектом в реализации без ожидания. ^[39] Объекты с числом консенсуса могут реализовать любой объект с числом консенсуса или ниже, но не могут реализовать любой объект с более высоким числом консенсуса. Числа консенсуса формируют то, что называется иерархией объектов синхронизации Херлихи . ^[40] ${\displaystyle n}$ ${\displaystyle n}$

Согласно иерархии, регистры чтения/записи не могут решить консенсус даже в системе с 2 процессами. Структуры данных, такие как стеки и очереди, могут решить консенсус только между двумя процессами. Однако некоторые параллельные объекты являются универсальными (отмечены в таблице как ), что означает, что они могут решить консенсус среди любого количества процессов, и они могут имитировать любые другие объекты через последовательность операций. ^[39] ${\displaystyle \infty }$

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

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

Ссылки

1. Джордж Кулурис; Джин Доллимор ; Тим Киндберг (2001), Распределенные системы: концепции и проектирование (3-е изд.), Addison-Wesley, стр. 452, ISBN 978-0201-61918-8
2. Долев, Д.; Стронг, Х. Р. (1983). «Аутентифицированные алгоритмы для византийского соглашения». SIAM Journal on Computing . 12 (4): 656–666. doi :10.1137/0212045.
3. Gong, Li; Lincoln, Patrick; Rushby, John (1995). «Византийское соглашение с аутентификацией». Надежные вычисления для критически важных приложений . 10. Архивировано из оригинала 2020-01-05 . Получено 2019-05-28 .
4. Aguilera, MK (2010). "Спотыкаясь о консенсусные исследования: недоразумения и проблемы". Репликация . Конспект лекций по информатике. Том 5959. С. 59–72. doi :10.1007/978-3-642-11294-2_4. ISBN 978-3-642-11293-5.
5. Фишер, М. Дж .; Линч, Н. А .; Патерсон, М. С. (1985). «Невозможность распределенного консенсуса с одним неисправным процессом» (PDF) . Журнал ACM . 32 (2): 374–382. doi :10.1145/3149.214121. S2CID  207660233. Архивировано (PDF) из оригинала 30.01.2023 . Получено 13.11.2017 .
6. Aspnes, James (май 1993). «Time- and Space-Efficient Randomized Consensus» (Эффективный по времени и пространству рандомизированный консенсус). Journal of Algorithms . 14 (3): 414–431. doi :10.1006/jagm.1993.1022. Архивировано из оригинала 2023-02-16 . Получено 2020-10-28 .
7. Милошевич, Жарко; Мартин Хатл; Андре Шипер (2009). "Unifying Byzantine Consensus Algorithms with Weak Interactive Consistency" . Принципы распределенных систем . Конспект лекций по информатике. Том 5293. С. 300–314. CiteSeerX 10.1.1.180.4229 . doi :10.1007/978-3-642-10877-8_24. ISBN  978-3-642-10876-1. {{cite book}}: |journal=проигнорировано ( помощь )
8. Lamport, L. (1983). "Проблема слабых византийских генералов". Журнал ACM . 30 (3): 668. doi : 10.1145/2402.322398 . S2CID  1574706.
9. Фишер, Майкл Дж. «Проблема консенсуса в ненадежных распределенных системах (краткий обзор)» (PDF) . Архивировано из оригинала (PDF) 22 апреля 2014 г. . Получено 21 апреля 2014 г. .
10. Lamport, L. ; Shostak, R.; Pease, M. (1982). "The Byzantine Generals Problem" (PDF) . ACM Transactions on Programming Languages ​​and Systems . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . doi :10.1145/357172.357176. S2CID  55899582. Архивировано (PDF) из оригинала 2017-02-07 . Получено 2015-08-29 . 
11. Лампорт, Лесли; Маршалл Пиз; Роберт Шостак (апрель 1980 г.). «Достижение соглашения при наличии разломов» (PDF) . Журнал ACM . 27 (2): 228–234. CiteSeerX 10.1.1.68.4044 . doi :10.1145/322186.322188. S2CID  6429068. Архивировано (PDF) из оригинала 28.01.2007 . Получено 25.07.2007 . 
12. Аттия, Хагит (2004). Распределенные вычисления (2-е изд.). Уайли. стр. 101–103. ISBN 978-0-471-45324-6.
13. Биспинг, Бенджамин и др. (2016), «Механическая проверка конструктивного доказательства для FLP», в Blanchette, Jasmin Christian; Merz, Stephan (ред.), Интерактивное доказательство теорем , Lecture Notes in Computer Science, т. 9807, Springer International Publishing, стр. 107–122, doi :10.1007/978-3-319-43144-4_7, ISBN 978-3-319-43144-4
14. Берман, Петр; Гарай, Хуан А. (1993). «Голоса Cloture: n/4-устойчивый распределенный консенсус в t + 1 раундах». Теория вычислительных систем . 2. 26 : 3–19. doi :10.1007/BF01187072. S2CID  6102847.
15. Burrows, M. (2006). Служба блокировки Chubby для слабосвязанных распределенных систем (PDF) . Труды 7-го симпозиума по проектированию и внедрению операционных систем. Ассоциация USENIX Беркли, Калифорния, США. стр. 335–350. Архивировано (PDF) из оригинала 14.12.2009 . Получено 28.10.2014 .
16. Тушар, К.; Гриземер, Р.; Редстоун, Дж. (2007). Paxos Made Live – An Engineering Perspective (PDF) . Труды двадцать шестого ежегодного симпозиума ACM по принципам распределенных вычислений . Портленд, Орегон, США: ACM Press New York, NY, США. стр. 398–407. doi :10.1145/1281100.1281103. Архивировано из оригинала (PDF) 2014-12-12 . Получено 2008-02-06 .
17. LeBlanc, Heath J. (апрель 2013 г.). «Устойчивый асимптотический консенсус в надежных сетях». Журнал IEEE по избранным областям в коммуникациях . 31 (4): 766–781. CiteSeerX 10.1.1.310.5354 . doi :10.1109/JSAC.2013.130413. S2CID  11287513. 
18. Дибаджи, SM (май 2015). «Консенсус многоагентных систем второго порядка при наличии локально ограниченных неисправностей». Systems & Control Letters . 79 : 23–29. doi :10.1016/j.sysconle.2015.02.005.
19. Dibaji, SM (июль 2017 г.). «Устойчивый консенсус сетей агентов второго порядка: асинхронные правила обновления с задержками». Automatica . 81 : 123–132. arXiv : 1701.03430 . Bibcode :2017arXiv170103430M. doi :10.1016/j.automatica.2017.03.008. S2CID  7467466.
20. Бен-Ор, Майкл (1983). «Еще одно преимущество свободного выбора (расширенная аннотация): Полностью асинхронные протоколы соглашения». Труды второго ежегодного симпозиума ACM по принципам распределенных вычислений . стр. 27–30. doi : 10.1145/800221.806707 . S2CID  38215511.
21. Долев, Дэнни; ​​Фишер, Майкл Дж.; Фаулер, Роб; Линч, Нэнси; Стронг, Х. Рэймонд (1982). «Эффективный алгоритм для византийского соглашения без аутентификации». Информация и управление . 52 (3): 257–274. doi : 10.1016/S0019-9958(82)90776-8 .
22. Фельдман, Песеч; Микали, Сильвио (1997). «Оптимальный вероятностный протокол для синхронного византийского соглашения». SIAM Journal on Computing . 26 (4): 873–933. doi :10.1137/S0097539790187084.
23. Кац, Джонатан; Ку, Чиу-Юэнь (2006). Об ожидаемых протоколах с постоянным раундом для византийского соглашения . CRYPTO 2006. doi : 10.1007/11818175_27 .
24. Кастро, Мигель; Лисков, Барбара (1999). "Практическая византийская отказоустойчивость" (PDF) . Труды Третьего симпозиума по проектированию и внедрению операционных систем, Новый Орлеан, США, февраль 1999 г. Архивировано (PDF) из оригинала 2018-03-04 . Получено 2019-05-28 .
25. Миллер, Эндрю; Ся, Ю; Кроман, Кайл; Ши, Элейн ; Сонг, Дон (октябрь 2016 г.). «Медовый барсук протоколов BFT» (PDF) . CCS '16: Труды конференции ACM SIGSAC 2016 года по компьютерной и коммуникационной безопасности . стр. 31–42. doi :10.1145/2976749.2978399. Архивировано (PDF) из оригинала 03.06.2023 . Получено 04.07.2023 .
26. Авраам, Иттай; Девадас, Шринивас; Долев, Дэнни; ​​Наяк, Картик; Рен, Линг (11 сентября 2017 г.). «Эффективный синхронный византийский консенсус» (PDF) . Архив Cryptology ePrint . Статья 2017/307. Архивировано (PDF) из оригинала 4 июля 2023 г. . Получено 4 июля 2023 г. .
27. Микали, Сильвио (19 марта 2018 г.). «Византийское соглашение стало тривиальным» (PDF) . Кембридж, Массачусетс: CSAIL, MIT. Архивировано (PDF) из оригинала 7 декабря 2022 г. . Получено 28 мая 2019 г. .
28. Чен, Цзин; Микали, Сильвио (2016). «АЛЬГОРАНД». arXiv : 1607.01341v9 [cs.CR].
29. Ирфан, Умайр (18 июня 2019 г.). «Биткойн — пожиратель энергии. Откуда берется столько электричества?». Vox . Архивировано из оригинала 16 февраля 2023 г. Получено 28 августа 2019 г.
30. "Слияние - последствия для потребления электроэнергии и углеродного следа сети Ethereum". 7 сентября 2022 г. Архивировано из оригинала 5 сентября 2023 г. Получено 5 сентября 2023 г.
31. "Потребление электроэнергии на душу населения во всем мире в 2022 году по выбранным странам". Архивировано из оригинала 2023-09-05 . Получено 2023-09-05 .
32. Шварц, Дэвид; Янгс, Ноа; Бритто, Артур (2014). "Алгоритм консенсуса протокола Ripple" (PDF) . Ripple Labs (черновик). Архивировано (PDF) из оригинала 29-08-2017 . Получено 03-07-2023 .
33. Мария Борге; Элефтериос Кокорис-Когиас; Филипп Йованович; Линус Гассер; Николас Гейлли; Брайан Форд (29 апреля 2017 г.). Доказательство личности: редемократизация криптовалют без разрешения. Безопасность и конфиденциальность IEEE в блокчейне (IEEE S&B). doi :10.1109/EuroSPW.2017.46. Архивировано из оригинала 12 ноября 2020 г. Получено 21 декабря 2020 г.
34. Дивья Сиддарт; Сергей Ивлиев; Сантьяго Сири; Паула Берман (13 октября 2020 г.). «Кто наблюдает за стражами? Обзор субъективных подходов к устойчивости к Сивилле в протоколах доказательства личности». arXiv : 2008.05300 [cs.CR].
35. Форд, Брайан; Штраус, Джейкоб (апрель 2008 г.). Оффлайновый фонд для онлайн-ответственных псевдонимов. 1-й семинар по системам социальных сетей - SocialNets '08. стр. 31–36. doi :10.1145/1435497.1435503. ISBN 978-1-60558-124-8. Получено 28.10.2020 .
36. Гал Шахаф; Эхуд Шапиро; Нимрод Талмон (октябрь 2020 г.). Подлинные персональные идентификаторы и взаимные поручительства для устойчивого к Сивилле роста сообщества. Международная конференция по социальной информатике. arXiv : 1904.09630 . doi :10.1007/978-3-030-60975-7_24.
37. Дипак Марам; Харджаслин Малваи; Фань Чжан; Нерла Жан-Луи; Александр Фролов; Тайлер Келл; Тайрон Лоббан; Кристин Мой; Ари Джуэлс; Эндрю Миллер (28 сентября 2020 г.). «CanDID: децентрализованная идентификация Can-Do с совместимостью с устаревшими версиями, устойчивостью к атакам Сивиллы и подотчетностью» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г. Получено 28 октября 2020 г.
38. Мохаммад-Джавад Хаджиалихани; Мохаммад-Махди Джаханара (20 июня 2018 г.). «UniqueID: децентрализованное доказательство уникальности человека». arXiv : 1806.07583 [cs.CR].
39. Herlihy, Maurice (январь 1991 г.). "Wait-Free Synchronization" (PDF) . ACM Transactions on Programming Languages ​​and Systems . 11 (1): 124–149. doi :10.1145/114005.102808. S2CID  2181446. Архивировано (PDF) из оригинала 5 июня 2011 г. . Получено 19 декабря 2011 г. .
40. Имбс, Дэмиен; Рейналь, Мишель (25 июля 2010 г.). «Мультипликативная сила чисел консенсуса» (PDF) . Труды 29-го симпозиума ACM SIGACT-SIGOPS по принципам распределенных вычислений . Ассоциация вычислительной техники. стр. 26–35. doi :10.1145/1835698.1835705. ISBN 978-1-60558-888-9. S2CID  3179361. Архивировано (PDF) из оригинала 27 января 2022 г. . Получено 22 апреля 2021 г. .
41. Fich, Faith; Hendler, Danny; Shavit, Nir (25 июля 2004 г.). «О присущей слабости примитивов условной синхронизации». Труды двадцать третьего ежегодного симпозиума ACM по принципам распределенных вычислений . Ассоциация вычислительной техники. стр. 80–87. CiteSeerX 10.1.1.96.9340 . doi :10.1145/1011767.1011780. ISBN  1-58113-802-4. S2CID  9313205.

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

• Herlihy, M.; Shavit, N. (1999). "Топологическая структура асинхронной вычислимости". Journal of the ACM . 46 (6): 858. CiteSeerX  10.1.1.78.1455 . doi :10.1145/331524.331529. S2CID  5797174.
• Сакс, М.; Захароглу, Ф. (2000). «Соглашение о k-множестве без ожидания невозможно: топология общедоступных знаний». Журнал SIAM по вычислениям . 29 (5): 1449–1483. doi :10.1137/S0097539796307698.
• Башир, Имран. «Консенсус блокчейна». Консенсус блокчейна — введение в классические, блокчейн и квантовые протоколы консенсуса . ISBN 978-1-4842-8178-9 Apress, Беркли, Калифорния, 2022. doi :10.1007/978-1-4842-8179-6