Атомарная широковещательная рассылка: различия между версиями

Примерно в тот же период, когда впервые была опубликована работа Кристиана и др. [6], Чанг и Максемчук [3] предложили протокол атомарной широковещательной рассылки, основанный на протоколе передачи маркера и устойчивый к отказам процессоров. Кроме того, Карр [1] представил протокол глобального обновления Tandem, устойчивый к отказам процессоров.

Позже Кристиан [5] предложил расширение представленного здесь алгоритма, устойчивое к пропускам, в предположении, что система коммуникации состоит из <math>f + 1</math> независимых широковещательных каналов (где <math>f</math> – максимальное количество сбойных процессоров). По сравнению с описываем ниже протоколом более общего вида это расширение генерирует значительно меньше сообщений.

С момента выхода исследований Кристиана, Агили, Стронга и Долева [7] было опубликовано много работ, посвященных задаче атомарной широковещательной рассылки (и ее многочисленным вариантам). К примеру, Дефаго, Шипер и Урбан [8] рассмотрели более шестидесяти различных алгоритмов решения этой задачи, разделив их на пять различных классов и двенадцать вариантов. В упомянутом обзоре также рассмотрено множество альтернативных определений и приведены ссылки на примерно две сотни статей, связанных с этой темой. Эта область исследований по-прежнему очень активна, и каждый год публикуется множество новых результатов.

Чандра и Туэг [2] доказали эквивалентность между атомарной широковещательной рассылкой и ''задачей о достижении консенсуса''. Таким образом, любая задача, решаемая с помощью консенсуса, может быть решена с помощью атомарной широковещательной рассылки – и наоборот. Аналогичным образом, результаты о невозможности одинаково применимы к обеим задачам. Например, хорошо известно, что задача о достижении консенсуса, а значит и об организации атомарной широковещательной рассылки, не могут быть решены детерминированно в асинхронной системе в присутствии сбойного процесса [9].