Фундаментальная проблема распределенных вычислений и многоагентных систем заключается в достижении общей надежности системы при наличии ряда неисправных процессов. Это часто требует координации процессов для достижения консенсуса или согласования некоторого значения данных, которое необходимо во время вычислений. Примеры применения консенсуса включают согласование того, какие транзакции и в каком порядке фиксировать в базе данных, репликацию конечного автомата и атомарные широковещательные рассылки . Реальные приложения, часто требующие консенсуса, включают облачные вычисления , синхронизацию часов , PageRank , формирование мнения, интеллектуальные электросети и т. Д.оценка состояния , управление БПЛА (и несколькими роботами / агентами в целом), балансировка нагрузки , блокчейн и другие.
Описание проблемы
Проблема консенсуса требует соглашения между несколькими процессами (или агентами) для одного значения данных. Некоторые из процессов (агентов) могут давать сбой или быть ненадежными по другим причинам, поэтому протоколы консенсуса должны быть отказоустойчивыми или отказоустойчивыми. Процессы должны каким-то образом выдвигать свои кандидатские ценности, общаться друг с другом и согласовывать единую консенсусную ценность.
Проблема консенсуса - фундаментальная проблема в управлении многоагентными системами. Один из подходов к достижению консенсуса состоит в том, чтобы все процессы (агенты) пришли к соглашению о значении большинства. В этом контексте для большинства требуется, по крайней мере, на половину имеющихся голосов (где каждому процессу предоставляется голос). Однако один или несколько ошибочных процессов могут исказить результирующий результат, так что консенсус не может быть достигнут или достигнут неверно.
Протоколы, которые решают проблемы консенсуса, предназначены для работы с ограниченным количеством ошибочных процессов . Чтобы эти протоколы были полезными, они должны удовлетворять ряду требований. Например, в тривиальном протоколе все процессы могут выводить двоичное значение 1. Это бесполезно, и поэтому требование изменяется таким образом, что вывод должен каким-то образом зависеть от ввода. То есть выходное значение протокола консенсуса должно быть входным значением некоторого процесса. Другое требование состоит в том, что процесс может принять решение о выходном значении только один раз, и это решение не подлежит отмене. Процесс называется правильным при выполнении, если он не дает сбоев. Протокол консенсуса, допускающий сбои при остановке, должен удовлетворять следующим свойствам. [1]
- Прекращение
- В конце концов, каждый правильный процесс определяет какую-то ценность.
- Честность
- Если все правильные процессы предложили одно и то же значение , то любой правильный процесс должен решить .
- Соглашение
- Каждый правильный процесс должен согласовывать одно и то же значение.
В зависимости от приложения могут потребоваться различные варианты определения целостности . Например, более слабым типом целостности будет значение решения, равное значению, предложенному некоторым правильным процессом, а не обязательно всем. [1] Целостность условие также известно как действительности в литературе. [1]
Протокол, который может правильно гарантировать консенсус между n процессами, из которых не более t терпит неудачу, называется t-устойчивым .
При оценке производительности консенсусных протоколов интерес представляют два фактора: время выполнения и сложность сообщения . Время выполнения указывается в нотации Big O в количестве раундов обмена сообщениями как функция некоторых входных параметров (обычно количества процессов и / или размера входной области). Сложность сообщения относится к объему трафика сообщений, который генерируется протоколом. Другие факторы могут включать использование памяти и размер сообщений.
Модели вычислений
Различные модели вычислений могут определять «проблему консенсуса». Некоторые модели могут иметь дело с полносвязными графами, в то время как другие могут иметь дело с кольцами и деревьями. В некоторых моделях аутентификация сообщений разрешена, в то время как в других процессы полностью анонимны. Модели общей памяти, в которых процессы взаимодействуют посредством доступа к объектам в общей памяти, также являются важной областью исследований.
Каналы связи с прямой или переносимой аутентификацией
В большинстве моделей протокола связи участники общаются через аутентифицированные каналы. Это означает, что сообщения не анонимны, и получатели знают источник каждого сообщения, которое они получают. Некоторые модели предполагают более надежную, переносимую форму аутентификации, при которой каждое сообщение подписывается отправителем, так что получатель знает не только непосредственный источник каждого сообщения, но и участника, который изначально создал сообщение. Этот более строгий тип аутентификации достигается с помощью цифровых подписей, и когда доступна эта более строгая форма аутентификации, протоколы могут допускать большее количество ошибок. [2]
Две разные модели аутентификации часто называют моделями устного и письменного общения . В модели устной коммуникации непосредственный источник информации известен, тогда как в более сильных, письменных моделях коммуникации каждый шаг на пути получателя узнает не только непосредственный источник сообщения, но и историю коммуникации сообщения. [3]
Входы и выходы консенсуса
В наиболее традиционных протоколах консенсуса с одним значением , таких как Paxos , взаимодействующие узлы согласовывают одно значение, такое как целое число, которое может иметь переменный размер, чтобы кодировать полезные метаданные, такие как транзакция, зафиксированная в базе данных.
Частный случай проблемы консенсуса с одним значением, называемый двоичным консенсусом , ограничивает ввод и, следовательно, область вывода одной двоичной цифрой {0,1}. Хотя сами по себе протоколы бинарного консенсуса не очень полезны, они часто используются в качестве строительных блоков в более общих протоколах консенсуса, особенно для асинхронного консенсуса.
В многозначных протоколах консенсуса, таких как Multi-Paxos и Raft , цель состоит в том, чтобы согласовать не просто одно значение, а серию значений с течением времени, формируя постепенно растущую историю. В то время как многозначный консенсус может быть достигнут наивно путем последовательного выполнения нескольких итераций однозначного консенсусного протокола, многие оптимизации и другие соображения, такие как поддержка реконфигурации, могут сделать многозначные консенсусные протоколы более эффективными на практике.
Крах и византийские неудачи
Существует два типа сбоев, которым может подвергнуться процесс: сбой при сбое или византийский сбой . Сбой сбой происходит , когда процесс резко останавливается и не возобновляется. Византийские неудачи - это неудачи, к которым не предъявляются абсолютно никакие условия. Например, они могут возникнуть в результате злонамеренных действий злоумышленника. Процесс, в котором произошел византийский сбой, может отправлять противоречивые или противоречивые данные другим процессам, или он может засыпать, а затем возобновить работу после длительной задержки. Из двух типов неудач византийские неудачи гораздо более разрушительны.
Таким образом, протокол консенсуса, допускающий византийские отказы, должен быть устойчивым ко всем возможным ошибкам, которые могут произойти.
Более сильная версия консенсуса, допускающего византийские неудачи, дается путем усиления ограничения целостности:
- Честность
- Если правильный процесс решит , тогда должно быть, было предложено каким-то правильным процессом.
Асинхронные и синхронные системы
Проблема консенсуса может быть рассмотрена в случае асинхронных или синхронных систем. Хотя в реальном мире коммуникации часто являются асинхронными по своей природе, более практично и часто проще моделировать синхронные системы [4], учитывая, что асинхронные системы, естественно, связаны с большим количеством проблем, чем синхронные.
В синхронных системах предполагается, что все коммуникации осуществляются циклически . В одном раунде процесс может отправлять все требуемые сообщения, одновременно получая все сообщения от других процессов. Таким образом, никакое сообщение из одного раунда не может влиять на сообщения, отправленные в том же раунде.
Результат невозможности FLP для асинхронного детерминированного консенсуса
В полностью асинхронной распределенной системе с передачей сообщений, в которой хотя бы один процесс может иметь аварийный сбой , в знаменитом результате невозможности FLP было доказано, что детерминированный алгоритм для достижения консенсуса невозможен. [5] Такой результат невозможности возникает из-за наихудших сценариев планирования, которые маловероятны на практике, за исключением состязательных ситуаций, таких как интеллектуальный злоумышленник с отказом в обслуживании в сети. В большинстве обычных ситуаций планирование процессов имеет степень естественной случайности. [4]
В асинхронной модели некоторые виды сбоев могут обрабатываться синхронным протоколом консенсуса. Например, потеря канала связи может быть смоделирована как процесс, который потерпел византийский сбой.
Алгоритмы рандомизированного консенсуса могут обойти результат невозможности FLP за счет достижения как безопасности, так и живучести с подавляющей вероятностью, даже при наихудших сценариях планирования, таких как интеллектуальный злоумышленник с отказом в обслуживании в сети. [6]
Разрешенный консенсус против несанкционированного
Алгоритмы консенсуса традиционно предполагают, что набор участвующих узлов фиксирован и задан с самого начала: то есть какой-то предварительный (ручной или автоматический) процесс настройки разрешил определенной известной группе участников, которые могут аутентифицировать друг друга как членов группы. В отсутствие такой четко определенной закрытой группы с аутентифицированными членами атака Сибиллы на открытую консенсусную группу может победить даже византийский консенсусный алгоритм, просто создав достаточное количество виртуальных участников, чтобы преодолеть порог отказоустойчивости.
Permissionless протокол консенсуса, напротив, позволяет любому в сети присоединиться к динамично и участвовать без предварительного разрешения, но вместо этого вводит другую форму искусственной стоимости или барьер входа для смягчения атаки Сибил угрозы. Биткойн представил первый протокол консенсуса без разрешения, использующий доказательство работы и функцию регулировки сложности, в которой участники соревнуются, чтобы решить криптографические хеш- головоломки, и вероятностно зарабатывают право фиксировать блоки и получать соответствующие вознаграждения пропорционально затраченным ими вычислительным усилиям. Частично мотивированные высокой стоимостью энергии этого подхода, последующие протоколы консенсуса без разрешения предложили или приняли другие альтернативные правила участия для защиты от атак Sybil, такие как доказательство доли , доказательство места и доказательство полномочий .
Эквивалентность проблем согласования
Представляют интерес три проблемы согласования.
Прекращение надежной трансляции
Коллекция процессы, пронумерованные от к общаться, отправляя сообщения друг другу. Процесс должен передавать значение ко всем процессам, таким как:
- если процесс правильно, то каждый правильный процесс получает
- для любых двух правильных процессов каждый процесс получает одно и то же значение.
Это также известно как проблема генерала.
Консенсус
Формальные требования к протоколу консенсуса могут включать:
- Соглашение : все правильные процессы должны согласовывать одно и то же значение.
- Слабая валидность : для каждого правильного процесса его выход должен быть входом некоторого правильного процесса.
- Строгая достоверность : если все правильные процессы получают одно и то же входное значение, то все они должны вывести это значение.
- Завершение : все процессы должны в конечном итоге принять решение о выходном значении.
Слабая интерактивная согласованность
Для n процессов в частично синхронной системе (система чередует хорошие и плохие периоды синхронизации) каждый процесс выбирает частное значение. Процессы взаимодействуют друг с другом раундами, чтобы определить общедоступную ценность и сформировать вектор консенсуса со следующими требованиями: [7]
- если правильный процесс отправляет , то все правильные процессы получают либо или ничего (свойство целостности)
- все сообщения, отправленные в раунде правильным процессом, принимаются в одном раунде всеми правильными процессами (свойство согласованности).
Можно показать, что варианты этих проблем эквивалентны в том смысле, что решение проблемы в модели одного типа может быть решением другой проблемы в модели другого типа. Например, решение проблемы Weak Byzantine General в модели передачи сообщений с синхронной аутентификацией приводит к решению проблемы Weak Interactive Consistency. [8] Интерактивный алгоритм согласованности может решить проблему консенсуса, если каждый процесс выбирает значение большинства в своем векторе консенсуса в качестве значения консенсуса. [9]
Результаты разрешимости некоторых проблем согласования
Существует трет-упругие анонимный синхронный протокол , который решает византийскую проблему Generals , [10] [11] , еслии случай слабых византийских генералов [8], где количество отказов и количество процессов.
Для систем с процессоры, из которых являются византийскими, было показано, что не существует алгоритма, который решает проблему консенсуса для в модели устных сообщений . [12] Доказательство строится, сначала показывая невозможность для трехузлового случаяи используя этот результат, чтобы спорить о разделах процессоров. В модели письменных сообщений есть протоколы, которые могут выдерживать. [2]
В полностью асинхронной системе нет консенсусного решения, которое могло бы выдержать один или несколько сбоев, даже если требуется только свойство нетривиальности. [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] | Синхронный | Устный | полное общение | ||
Пиз-Шостак-Лампорт [10] | Синхронный | Написано | полное общение | ||
Бен-Ор [20] | Асинхронный | Устный | (ожидал) | ожидал раундов, когда | |
Dolev et al. [21] | Синхронный | Устный | полное общение | ||
Долев-Стронг [2] | Синхронный | Написано | полное общение | ||
Долев-Стронг [2] | Синхронный | Написано | полное общение | ||
Фельдман-Микали [22] | Синхронный | Устный | (ожидал) | ||
Кац-Ку [23] | Синхронный | Написано | (ожидал) | Требуется PKI | |
PBFT [24] | Асинхронный (безопасность) - Синхронный (живучесть) | Устный | |||
HoneyBadger [25] | Асинхронный | Устный | (ожидал) | за tx-связь - требует шифрования с открытым ключом | |
Abraham et al. [26] | Синхронный | Написано | |||
Византийское соглашение стало тривиальным [27] [28] | Синхронный | Подписи | (ожидал) | Требуется цифровая подпись |
Протоколы консенсуса без разрешения
Биткойн использует доказательство работы , функцию регулировки сложности и функцию реорганизации для достижения консенсуса без прав доступа в своей открытой одноранговой сети. Чтобы расширить блокчейн или распределенный реестр Биткойна , майнеры пытаются решить криптографическую головоломку, в которой вероятность нахождения решения пропорциональна вычислительным усилиям, затрачиваемым в хэшах в секунду. Узел, который первым решает такую головоломку, имеет предложенную им версию следующего блока транзакций, добавленную в реестр и в конечном итоге принятую всеми другими узлами. Поскольку любой узел в сети может попытаться решить проблему доказательства работы, атака Сибиллы в принципе невозможна, если у злоумышленника нет более 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] Объекты с согласованным числом может реализовать любой объект с согласованным числом или ниже, но не может реализовать объекты с более высоким согласованным числом. Согласованные числа образуют так называемую иерархию объектов синхронизации Херлихи. [39]
Номер консенсуса | Объекты |
---|---|
атомарные регистры чтения / записи , мьютекс | |
test-and-set , swap , fetch-and-add , очередь без ожидания или стек | |
... | ... |
n-регистровое присвоение | |
... | ... |
сравнение-и-обмен , загрузка-ссылка / сохранение-условное , [40] перемещение и подкачка из памяти в память, очередь с операцией просмотра, выборка и минусы, липкий байт |
Согласно иерархии регистры чтения / записи не могут достичь консенсуса даже в двухпроцессной системе. Структуры данных, такие как стеки и очереди, могут достичь консенсуса только между двумя процессами. Однако некоторые параллельные объекты универсальны (отмечены в таблице значком), что означает, что они могут достичь консенсуса между любым количеством процессов и могут имитировать любые другие объекты с помощью последовательности операций. [38]
Смотрите также
- Единый консенсус
- Квантовое византийское соглашение
- Византийская отказоустойчивость
Рекомендации
- ^ a b c Кулурис, Джордж; Жан Доллимор ; Тим Киндберг (2001), Распределенные системы: концепции и дизайн (3-е издание) , Addison-Wesley, стр. 452, ISBN 978-0201-61918-8
- ^ а б в г Долев, Д .; Сильный, HR (1983). «Аутентифицированные алгоритмы византийского соглашения». SIAM Journal on Computing . 12 (4): 656–666. DOI : 10.1137 / 0212045 .
- ^ Гонг, Ли; Линкольн, Патрик; Рашби, Джон (1995). «Византийское соглашение с аутентификацией» . Надежные вычисления для критически важных приложений . 10 .
- ^ а б Агилера, МК (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 .
- ^ Аспнес, Джеймс (май 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 года .
- ^ а б в Lamport, L .; Шостак, Р .; Пиз, М. (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 .
- ^ Аттия, Хагит (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.
- ^ С., Тушар; Griesemer, R; Редстоун Дж. (2007). Paxos Made Live - инженерная перспектива (PDF) . Материалы двадцать шестого ежегодного симпозиума ACM по принципам распределенных вычислений . Портленд, Орегон, США: ACM Press, Нью-Йорк, Нью-Йорк, США. С. 398–407. DOI : 10.1145 / 1281100.1281103 . Архивировано из оригинального (PDF) 12 декабря 2014 года . Проверено 6 февраля 2008 .
- ^ ЛеБлан, Хит Дж. (Апрель 2013 г.). «Устойчивый асимптотический консенсус в надежных сетях». Журнал IEEE по избранным областям коммуникаций . 31 (4): 766–781. CiteSeerX 10.1.1.310.5354 . DOI : 10.1109 / JSAC.2013.130413 . S2CID 11287513 .
- ^ Дибаджи, С.М. (май 2015 г.). «Консенсус мультиагентных систем второго порядка при наличии локально ограниченных неисправностей». Системы и контрольные письма . 79 : 23–29. DOI : 10.1016 / j.sysconle.2015.02.005 .
- ^ Дибаджи, С.М. (июль 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 . Неизвестный параметр
|book-title=
игнорируется ( справка );Цитировать журнал требует|journal=
( помощь ) - ^ Долев, Дэнни; Фишер, Майкл Дж .; Фаулер, Роб; Линч, Нэнси; Сильный, Х. Раймонд (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
- ^ Каковы альтернативные стратегии доказательства работы?
- ^ Мария Борге, Элефтериос Кокорис-Когиас, Филипп Йованович, Линус Гассер, Николас Гейли, Брайан Форд (29 апреля 2017 г.). Доказательство личности: восстановление демократии без разрешения криптовалют . IEEE Security & Privacy on the Blockchain (IEEE S&B) . DOI : 10.1109 / EuroSPW.2017.46 .CS1 maint: использует параметр авторов ( ссылка )
- ^ Дивья Сиддарт, Сергей Ивлиев, Сантьяго Сири, Паула Берман (13 октября 2020 г.). «Кто наблюдает за стражами? Обзор субъективных подходов к сопротивлению Сибиллы в протоколах подтверждения личности». arXiv : 2008.05300 [ cs.CR ].CS1 maint: использует параметр авторов ( ссылка )
- ^ Форд, Брайан; Штраус, Якоб (1 апреля 2008 г.). Автономный фонд для подотчетных псевдонимов в Интернете . 1-й семинар по системам социальных сетей - SocialNets '08 . С. 31–6. DOI : 10.1145 / 1435497.1435503 . ISBN 978-1-60558-124-8.
- ^ Гал Шахаф, Эхуд Шапиро, Нимрод Талмон (октябрь 2020 г.). Подлинные личные идентификаторы и взаимные гарантии для устойчивого роста сообщества Sybil . Международная конференция по социальной информатике . DOI : 10.1007 / 978-3-030-60975-7_24 .CS1 maint: использует параметр авторов ( ссылка )
- ^ Дипак Марам, Харджаслин Мальваи, Фан Чжан, Нерла Жан-Луи, Александр Фролов, Тайлер Келл, Тайрон Лоббан, Кристин Мой, Ари Джуэльс, Эндрю Миллер (28 сентября 2020 г.). «CanDID: децентрализованная идентификация, способная работать с унаследованной совместимостью, устойчивостью к Сибилле и подотчетностью» (PDF) .CS1 maint: использует параметр авторов ( ссылка )
- ^ Мохаммад-Джавад Хаджиалихани, Мохаммад-Махди Джаханара (20 июня 2018 г.). «UniqueID: децентрализованное доказательство уникальности человека». arXiv : 1806.07583 . Неизвестный параметр
|url=
игнорируется ( справка )CS1 maint: использует параметр авторов ( ссылка ) - ^ а б Херлихи, Морис. «Синхронизация без ожидания» (PDF) . Проверено 19 декабря 2011 года .
- ^ Имбс, Дэмиен; Рейналь, Мишель (25 июля 2010 г.). «Мультипликативная сила консенсусных чисел» (PDF) . Материалы 29-го симпозиума ACM SIGACT-SIGOPS по принципам распределенных вычислений . Ассоциация вычислительной техники: 26–35. DOI : 10.1145 / 1835698.1835705 . ISBN 9781605588889. S2CID 3179361 . Проверено 22 апреля 2021 года .
- ^ Фич, Вера; Хендлер, Дэнни; Шавит, Нир (25 июля 2004 г.). «О слабости, присущей примитивам условной синхронизации». Материалы двадцать третьего ежегодного симпозиума ACM по принципам распределенных вычислений . Ассоциация вычислительной техники: 80–87. CiteSeerX 10.1.1.96.9340 . DOI : 10.1145 / 1011767.1011780 . ISBN 1581138024. S2CID 9313205 .
дальнейшее чтение
- 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 .