Лекция
Привет, Вы узнаете о том , что такое консенсус, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое консенсус, задача византийских генералов, протоколы консенсуса , настоятельно рекомендую прочитать все из категории Высоконагруженные проекты.Паралельные вычисления. Суперкомпьютеры. Распределенные системы.
консенсус в общем случае трактуется как процесс принятия группой лиц единого решения, достижения согласия по какому-либо вопросу. При этом в качестве такого голосования не проводится - решение принимается на основе отсутствия возражений у большинства участников. Стоит отметить, что консенсусом называют не только сам процесс принятия решения, но именно принято в результате такой процедуры решения, то есть результат.
Фундаментальная проблема в распределенных вычислениях и многоагентных системах состоит в достижении общей надежности системы при наличии ряда неисправных процессов. Это часто требует координации процессов для достижения консенсуса или согласования некоторого значения данных, которое необходимо во время вычислений. Примеры применения консенсуса включают согласование того, какие транзакции и в каком порядке фиксировать в базе данных, репликацию конечного автомата и атомарные широковещательные рассылки . Реальные приложения, часто требующие консенсуса, включают облачные вычисления , синхронизацию часов , PageRank , формирование мнения, интеллектуальные электросети и т. Д.оценка состояния , управление БПЛА (и несколькими роботами / агентами в целом), балансировка нагрузки , блокчейн и другие.
Проблема консенсуса требует соглашения между несколькими процессами (или агентами) для одного значения данных. Некоторые процессы (агенты) могут давать сбой или быть ненадежными по другим причинам, поэтому протоколы консенсуса должны быть отказоустойчивыми или отказоустойчивыми. Процессы должны каким-то образом выдвигать свои кандидатские ценности, общаться друг с другом и согласовывать единую консенсусную ценность.
Проблема консенсуса - фундаментальная проблема в управлении многоагентными системами. Один из подходов к достижению консенсуса состоит в том, чтобы все процессы (агенты) пришли к соглашению о значении большинства. В этом контексте для большинства требуется, по крайней мере, на половину имеющихся голосов (где каждому процессу предоставляется голос). Однако один или несколько ошибочных процессов могут исказить результирующий результат, так что консенсус не может быть достигнут или достигнут неверно.
Протоколы, которые решают проблемы консенсуса, предназначены для работы с ограниченным количеством ошибочных процессов . Чтобы эти протоколы были полезными, они должны удовлетворять ряду требований. Например, в тривиальном протоколе все процессы могут выводить двоичное значение 1. Это бесполезно, и поэтому требование изменяется таким образом, что вывод каким-то образом должен зависеть от ввода. То есть выходное значение протокола консенсуса должно быть входным значением некоторого процесса. Другое требование состоит в том, что процесс может принять решение о выходном значении только один раз, и это решение не может быть отменено. Процесс называется правильным при выполнении, если он не дает сбоев. Протокол консенсуса, допускающий сбои при остановке, должен удовлетворять следующим свойствам.
завершенность
В конце концов, каждый правильный процесс определяет какую-то ценность.
целостность
Если все правильные процессы предложили одно и то же значение 
, то любой правильный процесс должен решить .
согласованность
Каждый правильный процесс должен согласовывать одно и то же значение.
В зависимости от приложения могут потребоваться различные варианты определения целостности . Например, более слабым типом целостности будет значение решения, равное значению, предложенному некоторым правильным процессом, а не обязательно всем. Целостность условие также известно как действительности в литературе.
Протокол, который может правильно гарантировать консенсус между n процессами, из которых не более t терпит неудачу, называется t-устойчивым .
При оценке производительности консенсусных протоколов интерес представляют два фактора: время выполнения и сложность сообщения . Время выполнения дается в нотации Big O в количестве раундов обмена сообщениями как функция некоторых входных параметров (обычно количества процессов и / или размера входной области). Сложность сообщения относится к объему трафика сообщений, генерируемого протоколом. Другие факторы могут включать использование памяти и размер сообщений.
Различные модели вычислений могут определять «проблему консенсуса». Некоторые модели могут иметь дело с полносвязными графами, а другие - с кольцами и деревьями. В некоторых моделях аутентификация сообщений разрешена, тогда как в других процессы полностью анонимны. Модели общей памяти, в которых процессы взаимодействуют посредством доступа к объектам в общей памяти, также являются важной областью исследований.
В большинстве моделей протокола связи участники общаются через аутентифицированные каналы. Это означает, что сообщения не анонимны, и получатели знают источник каждого сообщения, которое они получают. Некоторые модели предполагают более надежную, переносимую форму аутентификации, когда каждое сообщение подписывается отправителем, так что получатель знает не только непосредственный источник каждого сообщения, но и участника, который изначально создал сообщение. Этот более строгий тип аутентификации достигается с помощью цифровых подписей, и когда эта более строгая форма аутентификации доступна, протоколы могут допускать большее количество ошибок.
Две разные модели аутентификации часто называют моделями устного и письменного общения . В модели устной коммуникации непосредственный источник информации известен, тогда как в более сильных, письменных моделях коммуникации каждый шаг на пути получателя узнает не только непосредственный источник сообщения, но и историю коммуникации сообщения.
В большинстве моделей протокола консенсуса участники общаются по аутентифицирован каналам. Это означает, что сообщение не является анонимным, и получатели знают источник каждого сообщения, которое они получили. Некоторые модели предусматривают более строгую форму аутентификации, когда каждое сообщение подписывается отправителем, так что получатель знает не только непосредственный источник каждого сообщения, но и участника, который написал сообщение. Этот более строгий тип аутентификации достигается цифровыми подписями, а при наличии такой формы аутентификации протоколы могут допускать больше ошибок.
Две разные модели аутентификации часто называют устной и письменной моделями общения. В устной модели общения известное непосредственный источник информации, а в письменных моделях общения каждый шаг на пути к получателю изучает не только непосредственный источник сообщения, но и историю общения.
Существует два типа сбоев, которые могут возникнуть в процессе: сбой или византийская неудача. Крах происходит, когда процесс внезапно останавливается и не может быть обновленным. Византийская ошибка - это неудачи, при которых абсолютно никаких условий не навязывается. Например, они могут возникнуть в результате злонамеренных действий противника.
Рассмотрим подробно задачу византийских генералов .
Византийский консенсус - общее определение задачи взаимодействия нескольких участников сети между собой, расположенных удаленно и получают задание из центра. Причем часть участников сети, включая сам центр, могут оказаться злоумышленниками. Другими словами, алгоритм византийского протокола должен обеспечить коммуникацию между удаленными участниками сети, исключив обманные операции, то есть безопасность транзакций.
Идея византийского консенсуса появилась в 80-х годах прошлого века. Его суть заключается в следующем. Византия накануне битвы. Армия византийцев состоит, например, из 4 легионов, которые находятся друг от друга на расстоянии. В определенное время каждый из генералов легионов получает от руководящего центра приказ идти в атаку или отступать. Развитие событий следующее:
Задача понятна, но где гарантия, что среди генералов форуме предателей, которые выполнят приказ наоборот? И где гарантия, что сам главнокомандующий не окажется предателем, отправив различные приказы разным генералам? Вывод: генералы должны обменяться друг с другом информацией, исключив ошибочные данные. Точнее, они должны обменяться информацией о численности легионов, верных Византии, и сделать выводы о численности легиона предателей. Задача предусматривает, что при N количества генералов предателями могут оказаться N-1.
Принцип согласия заключается в том, чтобы все верные генералы в результате обмена информацией пришли к одинаковому решению, проигнорировав данные от генерал-предателя. Вернемся к примеру. Принцип обмена информацией заключается в следующем:
И логично, что по трем генералам цифры будут одинаковыми во всех трех блоках и только по одному будут разногласия.
Таким образом, верные генералы приходят к соглашению, исключая мнению предателя. Пример упрощенный, но наглядно показывает, как участники сети приходят к единому решению, исключая ложные.
Проблема консенсуса может быть рассмотрена в асинхронных или синхронных системах. Хотя связь в реальном мире часто по своей сути асинхронный, моделирование синхронных систем более практичное и часто проще, учитывая, что асинхронные системы естественным образом связаны с большим количеством проблем, чем синхронные.
В синхронных системах предполагается, что все коммуникации проходят в рамках сессии. За одну сессию процесс может отправить все необходимые ему сообщение, получая при этом все сообщения от других процессов. Таким образом, ни одно сообщение из одной сессии не может влиять на сообщения, отправленные в той же сессии.
В полностью асинхронной системе не существует единого решения, которое может допустить одну или более ошибок, даже если требуется лишь свойство нетривиальности. Этот результат иногда называют доказательством невозможности FLP, названным в честь авторов Майкла Дж. Фишера [en] , Нэнси Линч и Майка Патерсона [en] , которые получили премию Дейкстры за эту большую работу. Результат FLP не говорит о том, что консенсуса никогда нельзя достичь: только то, что по предположениям модели ни один алгоритм не может всегда достичь консенсуса в ограниченное время.
В наиболее традиционных протоколах консенсуса с одним значением , таких как Paxos , взаимодействующие узлы согласовывают одно значение, такое как целое число, которое может иметь переменный размер, чтобы кодировать полезные метаданные, такие как транзакция, зафиксированная в базе данных.
Особый случай проблемы консенсуса с одним значением, называемый двоичным консенсусом , ограничивает ввод и, следовательно, область вывода одной двоичной цифрой {0,1}. Хотя сами по себе протоколы бинарного консенсуса не очень полезны, они часто используются в качестве строительных блоков в более общих протоколах консенсуса, особенно для асинхронного консенсуса.
В протоколах многозначного консенсуса, таких как Multi-Paxos и Raft , цель состоит в том, чтобы согласовать не просто одно значение, а серию значений с течением времени, формируя постепенно растущую историю. Хотя многозначный консенсус может быть достигнут наивно, выполняя несколько итераций однозначного консенсусного протокола подряд, многие оптимизации и другие соображения, такие как поддержка реконфигурации, могут сделать многозначные консенсусные протоколы более эффективными на практике.
Существует два типа сбоев, которым может подвергнуться процесс: сбой в результате сбоя или византийский сбой . Сбой сбой происходит , когда процесс резко останавливается и не возобновляется. Византийские неудачи - это неудачи, к которым не предъявляются абсолютно никакие условия. Например, они могут возникнуть в результате злонамеренных действий злоумышленника. Процесс, в котором произошел византийский сбой, может отправлять противоречивые или противоречивые данные другим процессам, или он может засыпать, а затем возобновить работу после длительной задержки. Из двух типов неудач византийские неудачи гораздо более разрушительны.
Таким образом, протокол консенсуса, допускающий византийские отказы, должен быть устойчивым ко всем возможным ошибкам, которые могут произойти.
Более сильная версия консенсуса, допускающего византийские неудачи, дается путем усиления ограничения целостности:
Честность
Если правильный процесс решит , тогда должно быть, было предложено каким-то правильным процессом.
Проблема консенсуса может быть рассмотрена в случае асинхронных или синхронных систем. Об этом говорит сайт https://intellect.icu . Хотя обмен данными в реальном мире часто является асинхронным по своей природе, более практично и часто проще моделировать синхронные системы , учитывая, что асинхронные системы, естественно, связаны с большим количеством проблем, чем синхронные.
В синхронных системах предполагается, что все коммуникации осуществляются циклически . В одном раунде процесс может отправлять все требуемые сообщения, одновременно получая все сообщения от других процессов. Таким образом, никакое сообщение из одного раунда не может влиять на сообщения, отправленные в том же раунде.
В полностью асинхронной распределенной системе с передачей сообщений, в которой по крайней мере один процесс может иметь аварийный сбой , в знаменитом результате невозможности FLP было доказано, что детерминированный алгоритм для достижения консенсуса невозможен. Этот результат невозможности возникает из-за наихудших сценариев планирования, которые маловероятны на практике, за исключением состязательных ситуаций, таких как интеллектуальный злоумышленник с отказом в обслуживании в сети. В большинстве обычных ситуаций планирование процессов имеет степень естественной случайности.
В асинхронной модели некоторые виды сбоев могут обрабатываться синхронным протоколом консенсуса. Например, потеря канала связи может быть смоделирована как процесс, в котором произошел византийский сбой.
Алгоритмы рандомизированного консенсуса могут обойти результат невозможности FLP за счет достижения как безопасности, так и живучести с подавляющей вероятностью, даже при наихудших сценариях планирования, таких как интеллектуальный злоумышленник с отказом в обслуживании в сети.
Алгоритмы консенсуса традиционно предполагают, что набор узлов-участников фиксирован и задан с самого начала: то есть какой-то предварительный (ручной или автоматический) процесс настройки разрешил конкретную известную группу участников, которые могут аутентифицировать друг друга как членов группы. . В отсутствие такой четко определенной закрытой группы с аутентифицированными членами атака Сибиллы на открытую консенсусную группу может победить даже византийский алгоритм консенсуса, просто создав достаточное количество виртуальных участников, чтобы преодолеть порог отказоустойчивости.
Permissionless протокол консенсуса, напротив, позволяет любому в сети присоединиться к динамично и участвовать без предварительного разрешения, но вместо этого вводит другую форму искусственной стоимости или барьер входа для смягчения атаки Сибил угрозы. Биткойн представил первый протокол консенсуса без разрешения, основанный на криптографическом доказательстве работы , в котором участники соревнуются, чтобы решить криптографический хеш.головоломки, и с вероятностью заработайте право фиксировать блоки и зарабатывать связанные вознаграждения пропорционально затраченным вычислительным усилиям. Частично мотивированные высокой стоимостью энергии этого подхода, последующие протоколы консенсуса без разрешения предложили или приняли другие альтернативные правила участия для защиты от атак Sybil, такие как доказательство доли , доказательство пространства и доказательство полномочий .
Проблемы консенсуса, представляющие интерес, заключаются в следующем.
Коллекция процессов n, пронумерованных от 0 до n-1, отправляет сообщения друг другу. Процесс 0 должен передать значение всем процессам так, чтобы:
Формальные требования для согласованного протокола могут включать:
согласованность
Все процессы должны согласовывать одно и то же значение.
слабая вероятность
Для каждого правильного процесса его выходные данные должны быть входными данными какого-то правильного процесса.
сильная вероятность
Если все процессы получают одно и то же значение, то все они должны вывести это значение.
завершенность
Все процессы должны принять решение о исходное значение.
Для n процессов в частично синхронной системе (система дежурит хорошие и плохие периоды синхронизации), каждый процесс выбирает частное значение. Процессы обмениваются данными друг с другом в сессии, чтобы определить общедоступную ценность и создать согласованный вектор со следующими требованиями:
Существует трет-упругие анонимный синхронный протокол , который решает византийскую проблему Generals , [10] [11] , если
и случай слабых византийских генералов , где
количество отказов и 
количество процессов.
Для систем с процессоры, из которых 
являются византийскими, было показано, что не существует алгоритма, который решает проблему консенсуса для 
в модели устных сообщений . [12] Доказательство строится, сначала показывая невозможность для случая трех узлов
и используя этот результат, чтобы спорить о разделах процессоров. В модели письменных сообщений есть протоколы, которые могут
.
В полностью асинхронной системе нет консенсусного решения, которое могло бы выдержать один или несколько сбоев, даже если требуется только свойство нетривиальности. Этот результат иногда называют доказательством невозможности FLP по имени авторов Майкла Дж. Фишера , Нэнси Линч и Майка Патерсона , получивших премию Дейкстры за эту важную работу. Результат FLP был механически подтвержден на предмет соответствия даже при допущении о справедливости . [13] Однако FLP не утверждает, что консенсус никогда не может быть достигнут: просто, согласно предположениям модели, ни один алгоритм не может всегда достичь консенсуса за ограниченное время. На практике это маловероятно.
Другие протоколы, которыми могут пользоваться криптовалюта , включают доказательство важности, доказательство расположения, доказательство активности, доказательство прошедшего времени. Все они рассматриваются как альтернатива доказательства работы, опять же из-за обилия вычислительной энергии, необходимой последнему.
Многие стратегических игр в режиме реального времени используют модифицированный протокол Lockstep [en] как протокол консенсуса для управления состоянием игры между игроками. В результате каждой игровой действия дельта-состояние игровой трансляции передается всем другим игрокам, а также хэш общего состояния игры. Каждый игрок подтверждает изменение, применяя дельту к собственному игрового состояния и сравнивая хэши игрового состояния. Если хэши не согласны, тогда происходит голосования, а тех игроков, чей игровой состояние находится в меньшинстве, отключают и изымают из игры (известная как десинхронизация).
Другой известный подход называется алгоритмами типа MSR, которые широко используются от информатики теории управления.
Паксос алгоритм консенсус Лэмпорт , и варианты его , такие как Плот , которые 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, широко используется от информатики до теории управления.
| Источник | Синхронность | Аутентификация | Порог | Раундов | Ноты |
|---|---|---|---|---|---|
| Pease-Shostak-Lamport | Синхронный | Устный |  |
 |
полное общение  |
| Pease-Shostak-Lamport | Синхронный | Написано |  |
|
полное общение |
| Ben-Or | Асинхронный | Устный |  |
 (ожидается) |
ожидается  раундов, когда  |
| Dolev et al. [21] | Синхронный | Устный | |
 |
полное общение  |
| Dolev-Strong | Синхронный | Написано | |
|
полное общение  |
| Dolev-Strong | Синхронный | Написано | |
 |
полное общение  |
| Feldman-Micali | Синхронный | Устный | |
(ожидается) |
|
| Katz-Koo | Синхронный | Написано |  |
(ожидается) |
Требуется PKI |
| PBFT [24] | Асинхронный (безопасность) - Синхронный (живучесть) | Устный | |
||
| HoneyBadger [25] | Асинхронный | Устный | |
 (ожидается) |
за передачу данных  - требует шифрования с открытым ключом |
| Abraham et al. [26] | Синхронный | Написано | |
 |
|
| Византийское соглашение ставшее тривиальным | Синхронный | Подписи | |
 (ожидается) |
Требуется цифровая подпись |
| Название | принцип | производительность | завершенность |
|---|---|---|---|
| Proof-of-Work (PoW - доказательство работы) | Трудно найти решение, но легко проверить результат. | низкая | вероятностная |
| Proof-of-Stake (PoS - доказательство доли) | Сеть доверяет валидатор, который ставит свои собственные ресурсы в залог за возможность создавать блоки: чем больше доля, тем выше вероятность, что сеть позволит создании блока. | высокая | вероятностная |
| Delegated Proof-of-Stake (DPoS) (Делегированный доказательство доли) | Участники делегируют производство новых блоков небольшой и фиксированного количества избранных валидаторов. Высокая конкуренция, но очень выгодна. | высокая | вероятностная |
| Proof-of-Activity (PoA) (Доказательство активности) | Гибрид PoW и PoS. | низкая | вероятностная |
| Proof-of-Location (PoL) (Доказательство расположения) | Используются маячки, чтобы заметить узел в синхронном состоянии, а затем отметить временным штампом ее присутствие. | средняя | немедленная |
| Proof-of-Importance (PoI) (Доказательство важности) | Как и PoS, но с дополнительными свойствами, которые влияют на ваш рейтинг. | высокая | вероятностная |
| Proof-of-Elapsed-Time (PoET) (Доказательство прошедшего времени) | Блоки создаются в среде с равными периодами. | средняя | вероятностная |
доказательство работы (Proof-of-Work, PoW ), типичный случай: битовые сетевые кредиты
Доказательство интереса (Proof-of-Stake, PoS , также переведенное доказательство владения), типичный случай: Ethernet Square
Delegated-Proof-of-Stake (DPoS), типичный случай: EOS
Типичный случай Proof-of-space (Proof-of-space, PoSpace, также известный как Proof-of-Capacity, PoC): Filecoin
Паксос
Биткойн использует доказательство работы для достижения консенсуса без разрешения в своей открытой одноранговой сети. Чтобы расширить блокчейн или распределенный реестр Биткойна , майнеры пытаются решить криптографическую головоломку, в которой вероятность нахождения решения пропорциональна вычислительным усилиям, затрачиваемым в хэшах в секунду. Узел, который первым решает такую головоломку, имеет предложенную версию следующего блока транзакций, добавленную в реестр и в конечном итоге принятую всеми другими узлами. Поскольку любой узел в сети может попытаться решить проблему доказательства работы, атака Sybil в принципе невозможна, если у злоумышленника нет более 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]
| Номер консенсуса | Объекты |
|---|---|
 |
Регистры чтения / записи |
 |
тест и установка, замена, выборка и добавление, очередь, стек |
| ... | ... |
 |
n-регистровое присвоение |
| ... | ... |
 |
Перемещение и подкачка из памяти в память, расширенная очередь, сравнение и подкачка, выборка и минусы, липкий байт |
Число консенсуса в иерархии означает максимальное количество процессов в системе, которые могут достичь консенсуса по данному объекту. Объекты с более высоким числом консенсуса не могут быть реализованы объектами с более низким числом консенсуса.
Согласно иерархии, регистры чтения / записи не могут достичь консенсуса даже в двухпроцессной системе. Структура данных, такая как стек, очередь и т. Д., Может обеспечить консенсус между двумя процессами. Почему эти объекты не могут достичь консенсуса между большим количеством процессов? Эффективный способ доказать это - воспользоваться преимуществом двойственности. Предположим, что выход является двоичным, состояние является бивалентным, если оба из двух выходов возможны, и если выход, достижимый из состояния, равен только 0/1, состояние называется 0-валентным / 1-валентным. Основная идея состоит в том, чтобы создать противоречие, выполнив некоторые операции, чтобы получить состояние, которое одновременно является 0-валентным и 1-валентным.
Однако некоторые параллельные объекты универсальны, что означает, что они могут достигать консенсуса между любым количеством процессов и могут имитировать любые другие объекты. Способ моделирования других объектов с помощью универсальных объектов состоит в построении последовательности операций с этим параллельным объектом. [38]
Анализ данных, представленных в статье про консенсус, подтверждает эффективность применения современных технологий для обеспечения инновационного развития и улучшения качества жизни в различных сферах. Надеюсь, что теперь ты понял что такое консенсус, задача византийских генералов, протоколы консенсуса и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Высоконагруженные проекты.Паралельные вычисления. Суперкомпьютеры. Распределенные системы
Комментарии
Оставить комментарий
Высоконагруженные проекты.Паралельные вычисления. Суперкомпьютеры. Распределенные системы
Термины: Высоконагруженные проекты.Паралельные вычисления. Суперкомпьютеры. Распределенные системы