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

Лэмпорт [ ] предложил один из первых опубликованных алгоритмов для решения проблемы упорядочивания при рассылке сообщений в распределенных системах. Этот алгоритм, представленный как ядро алгоритма взаимного исключения, работает в полностью асинхронной системе (т. е. системе, в которой нет ограничений на скорость процессора или задержку связи), но не выносит сбоев. Хотя рассматриваемые ниже алгоритмы опираются на физические часы, а не на логические часы Лэмпорта, используемый для упорядочивания сообщений принцип, по сути, остался тем же: сообщения содержат временную метку времени их отправки и доставляются в порядке возрастания временной метки, используя имя процессора-отправителя для сообщений с одинаковыми временными метками.

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

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

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

Хадзилакос и Туэг [ ] представили систематическую классификацию спецификаций для вариантов атомарной широковещательной рассылки, а также для других связанных с рассылками проблем, таких как надежная широковещательная рассылка, рассылка типа FIFO или каузальная рассылка.

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