В отказоустойчивых распределенных вычислениях атомарная широковещательная рассылка или широковещательная рассылка в полном порядке - это широковещательная рассылка , при которой все правильные процессы в системе из нескольких процессов получают один и тот же набор сообщений в одном и том же порядке; то есть та же последовательность сообщений. [1] [2] Трансляция называется « атомарной », потому что она либо в конечном итоге завершается правильно для всех участников, либо все участники прерываются без побочных эффектов. Атомарные широковещательные рассылки - важный примитив распределенных вычислений.
Характеристики
От протокола атомарной широковещательной передачи обычно требуются следующие свойства:
- Срок действия: если правильный участник передает сообщение, то в конечном итоге его получат все правильные участники.
- Единое соглашение: если один правильный участник получает сообщение, то все правильные участники в конечном итоге получат это сообщение.
- Единая целостность: сообщение получено каждым участником не более одного раза и только в том случае, если оно ранее транслировалось.
- Единый общий порядок: сообщения полностью упорядочены в математическом смысле; то есть, если какой-либо правильный участник сначала получает сообщение 1, а второй - сообщение 2, то каждый другой правильный участник должен получить сообщение 1 перед сообщением 2.
Rodrigues и Raynal [3] и Schiper et al. [4] несколько иначе определяют свойства целостности и достоверности атомарной трансляции.
Обратите внимание, что общий порядок не эквивалентен порядку FIFO , который требует, чтобы если процесс отправил сообщение 1 до того, как он отправил сообщение 2, то все участники должны получить сообщение 1 до получения сообщения 2. Это также не эквивалентно «причинному порядку», где если сообщение 2 «зависит от» или «происходит после» сообщения 1, тогда все участники должны получить сообщение 2 после получения сообщения 1. Хотя это сильное и полезное условие, полный порядок требует только того, чтобы все участники получали сообщения в одном и том же порядке, но это действительно так. не накладывайте других ограничений на этот порядок. [5]
Отказоустойчивость
Разработать алгоритм для атомарных широковещательных рассылок относительно легко, если предположить, что компьютеры не откажутся. Например, если нет сбоев, атомарная широковещательная рассылка может быть достигнута просто за счет того, что все участники общаются с одним «лидером», который определяет порядок сообщений, а другие участники следуют за лидером.
Однако настоящие компьютеры неисправны; они терпят неудачу и восстанавливаются после неудачи в непредсказуемые, возможно, неподходящие моменты. Например, в алгоритме следования за лидером, что, если лидер выйдет из строя в неподходящий момент? В такой среде сложно достичь атомных радиопередач. [1] Был предложен ряд протоколов для выполнения атомарной широковещательной рассылки при различных предположениях о сети, моделях отказа, наличии аппаратной поддержки многоадресной рассылки и так далее. [2]
Эквивалентно консенсусу
Для выполнения условий атомарной трансляции участники должны эффективно «согласовать» порядок получения сообщений. Участники, восстанавливающиеся после сбоя, после того, как другие участники «согласовали» порядок и начали получать сообщения, должны быть в состоянии изучить и соблюдать согласованный порядок. Такие соображения показывают, что в системах с аварийными отказами атомарная трансляция и консенсус являются эквивалентными проблемами. [6]
Значение может быть предложено процессом для достижения консенсуса путем атомарной широковещательной рассылки, и процесс может определить значение, выбрав значение первого сообщения, которое он получает атомарно. Таким образом, консенсус можно свести к атомарной трансляции.
И наоборот, группа участников может атомарно транслировать сообщения, достигая консенсуса в отношении первого сообщения, которое должно быть получено, с последующим достижением консенсуса по следующему сообщению и так далее, пока все сообщения не будут получены. Таким образом, атомная трансляция сводится к консенсусу. Более формально и более подробно это продемонстрировали Ксавье Дефаго и др. [2]
Фундаментальный результат распределенных вычислений заключается в том, что достижение консенсуса в асинхронных системах, в которых может произойти даже один сбой, невозможно в самом общем случае. Это было показано в 1985 году Майклом Дж. Фишером , Нэнси Линч и Майком Патерсоном и иногда называется результатом FLP. [7] Поскольку консенсус и атомарная трансляция эквивалентны, FLP применяется также к атомарной трансляции. [5] Результат FLP не запрещает реализацию атомарной широковещательной передачи на практике, но требует принятия менее строгих предположений, чем FLP, в некоторых отношениях, таких как время процессора и связи.
Алгоритмы
Алгоритм Чандра-Toueg [6] является на основе консенсуса решение атомного вещания. Другое решение было предложено Родригесом и Рейналом. [3]
Протокол Zookeeper Atomic Broadcast (ZAB) является основным строительным блоком для Apache ZooKeeper , отказоустойчивой распределенной службы координации, которая лежит в основе Hadoop и многих других важных распределенных систем. [8] [9]
Кен Бирман предложил модель виртуального синхронного выполнения для распределенных систем, идея которой состоит в том, что все процессы наблюдают одни и те же события в одном и том же порядке. Полное упорядочение получаемых сообщений, как в атомарной широковещательной рассылке, является одним (хотя и не единственным) методом достижения практически синхронного приема сообщений.
Рекомендации
- ^ а б Кшемкаляни, Аджай; Сингхал, Мукеш (2008). Распределенные вычисления: принципы, алгоритмы и системы (электронная книга Google) . Издательство Кембриджского университета. С. 583 –585. ISBN 9781139470315.
- ^ а б в Дефаго, Ксавье; Шипер, Андре; Урбан, Петер (2004). «Алгоритмы широковещательной и многоадресной рассылки общего порядка» (PDF) . ACM Computing Surveys . 36 (4): 372–421. DOI : 10.1145 / 1041680.1041682 .
- ^ a b Родригес Л., Рейнал М.: Атомное вещание в асинхронных распределенных системах восстановления после сбоев [1] , ICDCS '00: Материалы 20-й Международной конференции по распределенным вычислительным системам (ICDCS 2000)
- ^ Ekwall, R .; Шипер, А. (2006). «Решение атомной трансляции с косвенным консенсусом». Международная конференция по надежным системам и сетям (DSN'06) (PDF) . С. 156–165. DOI : 10,1109 / dsn.2006.65 . ISBN 0-7695-2607-1.
- ^ а б Дермот Келли. «Групповое общение» .
- ^ а б Чандра, Тушар Дипак; Туег, Сэм (1996). «Детекторы ненадежных отказов для надежных распределенных систем». Журнал ACM . 43 (2): 225–267. DOI : 10.1145 / 226643.226647 .
- ^ Майкл Дж. Фишер, Нэнси А. Линч и Майкл С. Патерсон (1985). «Невозможность распределенного консенсуса с одним ошибочным процессом» (PDF) . Журнал ACM . 32 (2): 374–382. DOI : 10.1145 / 3149.214121 .CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Флавио П. Жункейра, Бенджамин К. Рид и Марко Серафини, Yahoo! Исследования (2011). «Заб: высокопроизводительное вещание для систем первичного резервирования». 2011 41-я Международная конференция IEEE / IFIP по надежным системам и сетям (DSN) . С. 245–256. DOI : 10,1109 / DSN.2011.5958223 . ISBN 978-1-4244-9233-6. S2CID 206611670 .CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Андре Медейрос (20 марта 2012 г.). «Протокол атомной трансляции ZooKeeper: теория и практика» (PDF) . Хельсинкский технологический университет - Лаборатория теоретической информатики .