Консенсус (информатика)

Фундаментальная проблема распределенных вычислений и многоагентных систем заключается в достижении общей надежности системы при наличии ряда неисправных процессов. Это часто требует координации процессов для достижения консенсуса или согласования некоторого значения данных, которое необходимо во время вычислений. Примеры применения консенсуса включают согласование того, какие транзакции и в каком порядке фиксировать в базе данных, репликацию конечного автомата и атомарные широковещательные рассылки . Реальные приложения, часто требующие консенсуса, включают облачные вычисления , синхронизацию часов , 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 было доказано, что детерминированный алгоритм для достижения консенсуса невозможен. ^[5] Такой результат невозможности возникает из-за наихудших сценариев планирования, которые маловероятны на практике, за исключением состязательных ситуаций, таких как интеллектуальный злоумышленник с отказом в обслуживании в сети. В большинстве обычных ситуаций планирование процессов имеет степень естественной случайности. ^[4]

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

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

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

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

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

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

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

Прерывание надежной трансляции [ править ]

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

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

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

Консенсус [ править ]

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

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

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

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

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

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

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

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

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

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

Некоторые протоколы консенсуса [ править ]

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

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

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

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

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

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

Протоколы консенсуса без разрешения [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

^ a b c Кулурис, Джордж; Жан Доллимор ; Тим Киндберг (2001), Распределенные системы: концепции и дизайн (3-е издание) , Addison-Wesley, стр. 452, ISBN 978-0201-61918-8
^ a b c d Долев, Д .; Сильный, HR (1983). «Аутентифицированные алгоритмы византийского соглашения». SIAM Journal on Computing . 12 (4): 656–666. DOI : 10.1137 / 0212045 .
^ Гонг, Ли; Линкольн, Патрик; Рашби, Джон (1995). «Византийское соглашение с аутентификацией» . Надежные вычисления для критически важных приложений . 10 .
^ a b Агилера, МК (2010). «Спотыкаясь о консенсусном исследовании: недопонимание и проблемы». Репликация . Конспект лекций по информатике. 5959 . С. 59–72. DOI : 10.1007 / 978-3-642-11294-2_4 . ISBN 978-3-642-11293-5.
^ а б Фишер, MJ ; Линч, штат Северная Каролина ; Патерсон, М.С. (1985). «Невозможность распределенного консенсуса с одним ошибочным процессом» (PDF) . Журнал ACM . 32 (2): 374–382. DOI : 10.1145 / 3149.214121 . S2CID 207660233 .
^ Aspnes, Джеймс (май 1993). «Рандомизированный консенсус, эффективный по времени и пространству» . Журнал алгоритмов . 14 (3): 414–431. DOI : 10.1006 / jagm.1993.1022 .
↑ Милошевич, Зарко; Мартин Хатл; Андре Шипер (2009). Унификация византийских алгоритмов консенсуса со слабой интерактивной согласованностью . Принципы распределенных систем, Конспект лекций по информатике . Конспект лекций по информатике. 5293 . С. 300–314 . CiteSeerX 10.1.1.180.4229 . DOI : 10.1007 / 978-3-642-10877-8_24 . ISBN 978-3-642-10876-1.
^ а б Лэмпорт, Л. (1983). «Проблема слабых византийских генералов». Журнал ACM . 30 (3): 668. DOI : 10,1145 / 2402,322398 . S2CID 1574706 .
^ Фишер, Майкл Дж. «Проблема консенсуса в ненадежных распределенных системах (краткий обзор)» (PDF) . Проверено 21 апреля 2014 года .
^ а б в Лэмпорт, Л .; Шостак, Р .; Пиз, М. (1982). «Проблема византийских генералов» (PDF) . Транзакции ACM по языкам и системам программирования . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . DOI : 10.1145 / 357172.357176 .
^ Лэмпорт, Лесли; Маршалл Пиз; Роберт Шостак (апрель 1980 г.). «Достижение соглашения при наличии неисправностей» (PDF) . Журнал ACM . 27 (2): 228–234. CiteSeerX 10.1.1.68.4044 . DOI : 10.1145 / 322186.322188 . S2CID 6429068 . Проверено 25 июля 2007 .
^ Аттия, Hagit (2004). Распределенные вычисления 2-е изд . Вайли. С. 101–103. ISBN 978-0-471-45324-6.
^ Биспинг, Бенджамин; и другие. (2016), Бланшетт, Жасмин Кристиан; Мерц, Стефан (ред.), Механическая проверка конструктивного доказательства для FLP , Lecture Notes in Computer Science, 9807 , Springer International Publishing, DOI : 10.1007 / 978-3-319-43144-4_7 , ISBN 978-3-319-43144-4
^ Берман, Петр; Хуан А. Гарай (1993). «Cloture Votes: n / 4-resilient Distributed Consensus в t + 1 раундах». Теория вычислительных систем . 2. 26 : 3–19. DOI : 10.1007 / BF01187072 . S2CID 6102847 .
^ Берроуз, М. (2006). Служба блокировки Chubby для слабосвязанных распределенных систем (PDF) . Труды 7-го симпозиума по проектированию и внедрению операционных систем . Ассоциация USENIX Беркли, Калифорния, США. С. 335–350.
^ C., Тушар; Griesemer, R; Редстоун Дж. (2007). Paxos Made Live - инженерная перспектива (PDF) . Материалы двадцать шестого ежегодного симпозиума ACM по принципам распределенных вычислений . Портленд, Орегон, США: ACM Press, Нью-Йорк, Нью-Йорк, США. С. 398–407. DOI : 10.1145 / 1281100.1281103 . Архивировано из оригинального (PDF) 12 декабря 2014 года . Проверено 6 февраля 2008 .
Перейти ↑ LeBlanc, Heath J. (апрель 2013 г.). «Устойчивый асимптотический консенсус в надежных сетях». Журнал IEEE по избранным областям коммуникаций . 31 (4): 766–781. CiteSeerX 10.1.1.310.5354 . DOI : 10.1109 / JSAC.2013.130413 . S2CID 11287513 .
^ Dibaji, SM (май 2015). «Консенсус мультиагентных систем второго порядка при наличии локально ограниченных неисправностей». Письма о системах и управлении . 79 : 23–29. DOI : 10.1016 / j.sysconle.2015.02.005 .
^ Dibaji, SM (июль 2017). «Устойчивый консенсус агентских сетей второго порядка: правила асинхронного обновления с задержками». Automatica . 81 : 123–132. arXiv : 1701.03430 . Bibcode : 2017arXiv170103430M . DOI : 10.1016 / j.automatica.2017.03.008 . S2CID 7467466 .
↑ Бен-Ор, Майкл (1983). «Еще одно преимущество свободного выбора (расширенная аннотация): полностью асинхронные протоколы согласования»: 27–30. DOI : 10.1145 / 800221.806707 . S2CID 38215511 . Cite journal requires |journal= (help)
^ Долев, Дэнни; Фишер, Майкл Дж .; Фаулер, Роб; Линч, Нэнси; Сильный, Х. Раймонд (1982). «Эффективный алгоритм византийского соглашения без аутентификации». Информация и контроль . 52 (3): 257–274. DOI : 10.1016 / S0019-9958 (82) 90776-8 .
^ Фельдман, Песеч; Микали, Сильвио (1997). Оптимальный вероятностный протокол для синхронного византийского соглашения . SIAM Journal on Computing (Технический отчет). DOI : 10,1137 / S0097539790187084 .
^ Кац, Джонатан; Ку, Чиу-Юэн (2006). Об ожидаемых протоколах постоянного раунда византийского соглашения . КРИПТО. DOI : 10.1007 / 11818175_27 .
^ Кастро, Мигель; Лисков, Барбара (1999). Практическая византийская отказоустойчивость (PDF) . OSDI.
^ Миллер, Эндрю; Ся, Ю; Кроман, Кайл; Ши, Элейн ; Песня, Рассвет (2016). Медоед протоколов BFT . CCS. DOI : 10.1145 / 2976749.2978399 .
^ Авраам, Иттай; Девадас, Шринивас; Долев, Дэнни; Наяк, Картик; Рен, Линг (2017). Эффективный синхронный византийский консенсус (Технический отчет).
^ Микали, Сильвио (2018). «Византийское соглашение стало тривиальным» (PDF) .
^ Чен, Цзин; Микали, Сильвио. «АЛГОРАНД». arXiv : 1607.01341v9 .
^ Ирфан, Умар (18 июня 2019). «Биткойн - это энергетик. Откуда все это электричество?» . Vox .
^ Шварц D, Янгс, Бритто А. 2014 Алгоритм консенсуса протокола Ripple
^ Каковы альтернативные стратегии доказательства работы?
^ Мария Borge, Элефтериос Kokoris-Kogias, Philipp Йованович, Линус Гассер, Николас Gailly, Брайан Форд (29 апреля 2017). Доказательство личности: восстановление демократии без разрешения криптовалют . IEEE Security & Privacy on the Blockchain (IEEE S&B) . DOI : 10.1109 / EuroSPW.2017.46 .CS1 maint: uses authors parameter (link)
^ Дивие Siddarth, Сергей Ивлии, Santiago Siri, Пол Берман (13 октября 2020). «Кто наблюдает за стражами? Обзор субъективных подходов к сопротивлению Сибиллы в протоколах подтверждения личности». arXiv : 2008.05300 [ cs.CR ].CS1 maint: uses authors parameter (link)
^ Форд, Брайан; Штраус, Якоб (1 апреля 2008 г.). Автономный фонд для подотчетных псевдонимов в Интернете . 1-й семинар по системам социальных сетей - SocialNets '08 . С. 31–6. DOI : 10.1145 / 1435497.1435503 . ISBN 978-1-60558-124-8.
^ Gal Shahaf, Эхуд Шапиро, Нимрод Talmon (октябрь 2020). Подлинные личные идентификаторы и взаимные гарантии для устойчивого роста сообщества Sybil . Международная конференция по социальной информатике . DOI : 10.1007 / 978-3-030-60975-7_24 .CS1 maint: uses authors parameter (link)
^ Дипак Мары, Harjasleen Malvai, Вентилятор Zhang, Нерли Жан-Луи, Александр Фролов, Тайлер Келл, Тайрон Лоббан, Кристин Moy, Ари Juels, Эндрю Миллер (28 сентябрь 2020). «CanDID: децентрализованная идентификация, способная работать с унаследованной совместимостью, устойчивостью к Сибилле и подотчетностью» (PDF) . CS1 maint: uses authors parameter (link)
^ Мохаммад Джавад Hajialikhani Мохаммад Махди Джаханар (20 июня 2018). «UniqueID: децентрализованное доказательство уникальности человека» (PDF) . arXiv : 1806.07583 . CS1 maint: uses authors parameter (link)
^ а б Херлихи, Морис. «Синхронизация без ожидания» (PDF) . Проверено 19 декабря 2011 года .

Дальнейшее чтение [ править ]

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

[coulouris-1] Кулурис, Джордж; Жан Доллимор ; Тим Киндберг (2001), Распределенные системы: концепции и дизайн (3-е издание) , Addison-Wesley, стр. 452, ISBN 978-0201-61918-8

[dolev_strong-2] Долев, Д .; Сильный, HR (1983). «Аутентифицированные алгоритмы византийского соглашения». SIAM Journal on Computing . 12 (4): 656–666. DOI : 10.1137 / 0212045 .

[GLR95-3] Гонг, Ли; Линкольн, Патрик; Рашби, Джон (1995). «Византийское соглашение с аутентификацией» . Надежные вычисления для критически важных приложений . 10 .

[aguilera_stumbling-4] Агилера, МК (2010). «Спотыкаясь о консенсусном исследовании: недопонимание и проблемы». Репликация . Конспект лекций по информатике. 5959 . С. 59–72. DOI : 10.1007 / 978-3-642-11294-2_4 . ISBN 978-3-642-11293-5.

[fischer_impossibility-5] а б Фишер, MJ ; Линч, штат Северная Каролина ; Патерсон, М.С. (1985). «Невозможность распределенного консенсуса с одним ошибочным процессом» (PDF) . Журнал ACM . 32 (2): 374–382. DOI : 10.1145 / 3149.214121 . S2CID 207660233 .

[6] Aspnes, Джеймс (май 1993). «Рандомизированный консенсус, эффективный по времени и пространству» . Журнал алгоритмов . 14 (3): 414–431. DOI : 10.1006 / jagm.1993.1022 .

[7] Милошевич, Зарко; Мартин Хатл; Андре Шипер (2009). Унификация византийских алгоритмов консенсуса со слабой интерактивной согласованностью . Принципы распределенных систем, Конспект лекций по информатике . Конспект лекций по информатике. 5293 . С. 300–314 . CiteSeerX 10.1.1.180.4229 . DOI : 10.1007 / 978-3-642-10877-8_24 . ISBN 978-3-642-10876-1.

[lamport_WBGP-8] а б Лэмпорт, Л. (1983). «Проблема слабых византийских генералов». Журнал ACM . 30 (3): 668. DOI : 10,1145 / 2402,322398 . S2CID 1574706 .

[9] Фишер, Майкл Дж. «Проблема консенсуса в ненадежных распределенных системах (краткий обзор)» (PDF) . Проверено 21 апреля 2014 года .

[PSL82-10] а б в Лэмпорт, Л .; Шостак, Р .; Пиз, М. (1982). «Проблема византийских генералов» (PDF) . Транзакции ACM по языкам и системам программирования . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . DOI : 10.1145 / 357172.357176 .

[11] Лэмпорт, Лесли; Маршалл Пиз; Роберт Шостак (апрель 1980 г.). «Достижение соглашения при наличии неисправностей» (PDF) . Журнал ACM . 27 (2): 228–234. CiteSeerX 10.1.1.68.4044 . DOI : 10.1145 / 322186.322188 . S2CID 6429068 . Проверено 25 июля 2007 .

[12] Аттия, Hagit (2004). Распределенные вычисления 2-е изд . Вайли. С. 101–103. ISBN 978-0-471-45324-6.

[flp_verification-13] Биспинг, Бенджамин; и другие. (2016), Бланшетт, Жасмин Кристиан; Мерц, Стефан (ред.), Механическая проверка конструктивного доказательства для FLP , Lecture Notes in Computer Science, 9807 , Springer International Publishing, DOI : 10.1007 / 978-3-319-43144-4_7 , ISBN 978-3-319-43144-4

[14] Берман, Петр; Хуан А. Гарай (1993). «Cloture Votes: n / 4-resilient Distributed Consensus в t + 1 раундах». Теория вычислительных систем . 2. 26 : 3–19. DOI : 10.1007 / BF01187072 . S2CID 6102847 .

[15] Берроуз, М. (2006). Служба блокировки Chubby для слабосвязанных распределенных систем (PDF) . Труды 7-го симпозиума по проектированию и внедрению операционных систем . Ассоциация USENIX Беркли, Калифорния, США. С. 335–350.

[16] C., Тушар; Griesemer, R; Редстоун Дж. (2007). Paxos Made Live - инженерная перспектива (PDF) . Материалы двадцать шестого ежегодного симпозиума ACM по принципам распределенных вычислений . Портленд, Орегон, США: ACM Press, Нью-Йорк, Нью-Йорк, США. С. 398–407. DOI : 10.1145 / 1281100.1281103 . Архивировано из оригинального (PDF) 12 декабря 2014 года . Проверено 6 февраля 2008 .

[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] Dibaji, SM (май 2015). «Консенсус мультиагентных систем второго порядка при наличии локально ограниченных неисправностей». Письма о системах и управлении . 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 .

[B83-20] Бен-Ор, Майкл (1983). «Еще одно преимущество свободного выбора (расширенная аннотация): полностью асинхронные протоколы согласования»: 27–30. DOI : 10.1145 / 800221.806707 . S2CID 38215511 . Cite journal requires |journal= (help)

[DFFLS82-21] Долев, Дэнни; Фишер, Майкл Дж .; Фаулер, Роб; Линч, Нэнси; Сильный, Х. Раймонд (1982). «Эффективный алгоритм византийского соглашения без аутентификации». Информация и контроль . 52 (3): 257–274. DOI : 10.1016 / S0019-9958 (82) 90776-8 .

[FM97-22] Фельдман, Песеч; Микали, Сильвио (1997). Оптимальный вероятностный протокол для синхронного византийского соглашения . SIAM Journal on Computing (Технический отчет). DOI : 10,1137 / S0097539790187084 .

[KK06-23] Кац, Джонатан; Ку, Чиу-Юэн (2006). Об ожидаемых протоколах постоянного раунда византийского соглашения . КРИПТО. DOI : 10.1007 / 11818175_27 .

[PBFT-24] Кастро, Мигель; Лисков, Барбара (1999). Практическая византийская отказоустойчивость (PDF) . OSDI.

[HoneyBadger-25] Миллер, Эндрю; Ся, Ю; Кроман, Кайл; Ши, Элейн ; Песня, Рассвет (2016). Медоед протоколов BFT . CCS. DOI : 10.1145 / 2976749.2978399 .

[ADDNR17-26] Авраам, Иттай; Девадас, Шринивас; Долев, Дэнни; Наяк, Картик; Рен, Линг (2017). Эффективный синхронный византийский консенсус (Технический отчет).

[M18-27] Микали, Сильвио (2018). «Византийское соглашение стало тривиальным» (PDF) .

[28] Чен, Цзин; Микали, Сильвио. «АЛГОРАНД». arXiv : 1607.01341v9 .

[29] Ирфан, Умар (18 июня 2019). «Биткойн - это энергетик. Откуда все это электричество?» . Vox .

[30] Шварц D, Янгс, Бритто А. 2014 Алгоритм консенсуса протокола Ripple

[31] Каковы альтернативные стратегии доказательства работы?

[32] Мария Borge, Элефтериос Kokoris-Kogias, Philipp Йованович, Линус Гассер, Николас Gailly, Брайан Форд (29 апреля 2017). Доказательство личности: восстановление демократии без разрешения криптовалют . IEEE Security & Privacy on the Blockchain (IEEE S&B) . DOI : 10.1109 / EuroSPW.2017.46 .CS1 maint: uses authors parameter (link)

[33] Дивие Siddarth, Сергей Ивлии, Santiago Siri, Пол Берман (13 октября 2020). «Кто наблюдает за стражами? Обзор субъективных подходов к сопротивлению Сибиллы в протоколах подтверждения личности». arXiv : 2008.05300 [ cs.CR ].CS1 maint: uses authors parameter (link)

[34] Форд, Брайан; Штраус, Якоб (1 апреля 2008 г.). Автономный фонд для подотчетных псевдонимов в Интернете . 1-й семинар по системам социальных сетей - SocialNets '08 . С. 31–6. DOI : 10.1145 / 1435497.1435503 . ISBN 978-1-60558-124-8.

[35] Gal Shahaf, Эхуд Шапиро, Нимрод Talmon (октябрь 2020). Подлинные личные идентификаторы и взаимные гарантии для устойчивого роста сообщества Sybil . Международная конференция по социальной информатике . DOI : 10.1007 / 978-3-030-60975-7_24 .CS1 maint: uses authors parameter (link)

[36] Дипак Мары, Harjasleen Malvai, Вентилятор Zhang, Нерли Жан-Луи, Александр Фролов, Тайлер Келл, Тайрон Лоббан, Кристин Moy, Ари Juels, Эндрю Миллер (28 сентябрь 2020). «CanDID: децентрализованная идентификация, способная работать с унаследованной совместимостью, устойчивостью к Сибилле и подотчетностью» (PDF) . CS1 maint: uses authors parameter (link)

[37] Мохаммад Джавад Hajialikhani Мохаммад Махди Джаханар (20 июня 2018). «UniqueID: децентрализованное доказательство уникальности человека» (PDF) . arXiv : 1806.07583 . CS1 maint: uses authors parameter (link)

[hierarchy-38] а б Херлихи, Морис. «Синхронизация без ожидания» (PDF) . Проверено 19 декабря 2011 года .

[1]