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

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

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

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

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

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

Система G состоит из n распределенных процессоров и m каналов двухточечной связи. Канал не обязательно имеется между каждой парой процессоров, но предполагается, что коммуникационная сеть остается связной даже при наличии сбоев (как процессоров, так и каналов). Все процессоры имеют уникальные имена, и на них существует полный порядок (например, лексикографический).

Компонент (канал или процессор) считается ''исправным'', если его поведение соответствует спецификации, и ''сбойным'' в противном случае. Далее рассматриваются три класса отказов компонентов, а именно: пропуски, ошибки синхронизации и византийские ошибки.

• ''Византийская ошибка'' [12] (также известная как «задача византийских генералов» [https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B2%D0%B8%D0%B7%D0%B0%D0%BD%D1%82%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2]) имеет место в случае, когда компонент ведет себя не в соответствии со своей спецификацией – например, предоставляет выходной результат, отличный от заданного. В частности, рассматриваются обнаруживаемые с помощью аутентификации византийские ошибки, то есть такие, которые можно обнаружить с помощью протокола аутентификации сообщений, такого как коды исправления ошибок или цифровые подписи.

Кроме того, задержки при передаче и обработке данных, измеренные по часам исправного процессора, ограничены известной константой <math>\delta</math>. Это ограничение учитывает не только задержки при передаче и обработке, но и задержки, связанные с составлением расписания, перегрузкой, дрейфом или корректировкой часов. Такая модель называется моделью синхронной системы.

Временем рассеяния <math>d \delta</math> называется время, необходимое для распространения информации до всех корректных процессов в сохранившейся сети диаметром d при наличии не более <math>\lambda</math> отказов процессоров и A отказов каналов связи.

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

1. '''Допустимость''': если исправный процессор рассылает сообщение m, то он в конечном итоге доставляет m.

4. '''Равномерный полный порядок без пробелов''': если некоторый процессор доставляет сообщение m0 после сообщения m, то он доставляет m0 только после того, как он доставил m.

Все три протокола основаны на классическом алгоритме затопления, или рассеяния информации [14]. Каждое сообщение содержит временную метку T, имя инициирующего процессора s и обновление <math>\sigma</math>. Сообщение однозначно идентифицируется по паре (s, T). Основной протокол прост. Каждый процессор регистрирует каждое полученное сообщение до тех пор, пока оно не будет доставлено. Когда он получает сообщение, которого никогда не встречал раньше, он пересылает его всем соседним процессорам.

Первый протокол атомарной широковещательной рассылки, поддерживающий сбои типа «пропуск», рассматривает время завершения <math>\Delta_0</math> следующим образом.

(1) <math>\Delta_0 = \pi \delta + d \delta + \varepsilon</math>.

Крайний срок доставки <math>T + \Delta_0</math>o – это время, к которому процессор может быть уверен, что он получил копии всех сообщений с временной меткой T (или более ранними), которые могли быть получены некоторым исправным процессом.

Протокол работает следующим образом. Когда процессор инициирует атомарную широковещательную рассылку, он распространяет это сообщение, аналогично описанному выше алгоритму рассеяния. Основным исключением является то, что каждое сообщение, полученное после того, как показания локальных часов превысили крайний срок доставки этого сообщения, отбрасывается. Затем в локальное время <math>T + \Delta_0</math> процессор доставляет все сообщения, помеченные временной меткой T, в порядке возрастания имени отправляющего процессора. Наконец, он удаляет все копии сообщений из своих журналов.

Второй протокол расширяет первый, добавляя к сообщениям счетчик переходов (т. е. счетчик, увеличивающийся на 1 при каждой передаче сообщения). С помощью этой информации каждый передающий процессор может определить, когда сообщение является своевременным, то есть если сообщение с временной меткой T и счетчиком переходов h получено в момент времени U, то должно выполняться следующее условие:

Исходя из вышеуказанных предположений, третий протокол трансляции расширяет второй, добавляя к сообщениям подписи. Чтобы процессор (или канал связи) при использовании «византийского» протокола не мог подделать счетчик переходов, сообщение подписывается каждым процессором, который его передает. Например, сообщение, подписанное к процессорами <math>p_1, ..., p_k</math> выглядит следующим образом:

Здесь <math>\sigma</math> – обновление, T – временная метка, <math>p_1</math> – источник сообщения, а <math>s_i</math> – подпись, сгенерированная процессором <math>p_i</math>. Любое сообщение, для которого одна из подписей не может быть аутентифицирована, просто отбрасывается. Кроме того, если несколько обновлений, инициированных одним и тем же процессором p, имеют одинаковую временную метку, это означает, что данный процессор неисправен, и соответствующие обновления отбрасываются. Оставшаяся часть протокола аналогична второму случаю, где количество переходов определяется количеством подписей. Время завершения <math>\Delta_b</math> также вычисляется следующим образом:

'''Теорема 1. Если коммуникационная сеть G требует <math>x</math> шагов, то любой протокол атомарной широковещательной рассылки, способный перенести до <math>\pi</math> отказов процессоров и <math>\lambda</math> отказов каналов связи, имеет время завершения не менее <math>x \delta + \varepsilon</math>.'''

'''Теорема 2. Любой протокол атомарной широковещательной рассылки для гамильтоновой сети с n процессорами, допускающий n - 2 аутентифицируемых византийских ошибок процессоров, не может иметь время завершения меньше <math>(n - 1)(\delta + \varepsilon)</math>.'''

* [[Детекторы отказов]]