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

В работе Кристиана, Агили, Стронга и Долева [7] рассматривается задача атомарной широковещательной рассылки в системе с приблизительно синхронизированными часами и ограниченными задержками при передаче и обработке. Они представляют последовательные расширения алгоритма, позволяющие ему выносить ограниченное число пропусков, ошибок синхронизации или византийских ошибок, соответственно.

Лэмпорт [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> также вычисляется следующим образом:

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

В дополнение к трем представленным выше протоколам и их корректности, Кристиан и коллеги [ ] доказали следующие две нижних границы на время завершения протоколов атомарной широковещательной рассылки.

'''Теорема 1. Если коммуникационная сеть G требует x шагов, то любой протокол атомарной широковещательной рассылки, способный перенести до ж отказов процессоров и X отказов каналов связи, имеет время завершения не менее xS + ".'''

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

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

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

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