Атомарная широковещательная рассылка

Ключевые слова и синонимы

Атомарная групповая рассылка; широковещательная рассылка полного порядка; групповая рассылка полного порядка

Постановка задачи

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

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

Родственные работы

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

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

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

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

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

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

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

Нотация и предположения

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

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

• Пропуск имеет место, когда сбойный компонент не способен выдать заданный выходной результат (примером может служить потеря сообщения).

• Ошибка синхронизации имеет место, когда сбойный компонент пропускает выдачу заданного результата либо выдает его слишком рано или слишком поздно.

• Византийская ошибка [12] (также известная как «задача византийских генералов» [1]) имеет место в случае, когда компонент ведет себя не в соответствии со своей спецификацией – например, предоставляет выходной результат, отличный от заданного. В частности, рассматриваются обнаруживаемые с помощью аутентификации византийские ошибки, то есть такие, которые можно обнаружить с помощью протокола аутентификации сообщений, такого как коды исправления ошибок или цифровые подписи.

Каждый процессор p имеет доступ к локальным часам [math]\displaystyle{ C_p }[/math], обладающим следующими свойствами: (1) два отдельных показания часов дают разные значения; (2) часы [math]\displaystyle{ \varepsilon }[/math]-синхронизированы, что означает, что в любое реальное время t отклонение в показаниях часов любых двух процессоров p и q составляет не более [math]\displaystyle{ \varepsilon }[/math].

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

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

Постановка задачи

Задача атомарной широковещательной рассылки определяется в модели синхронной системы как примитив трансляции, удовлетворяющий следующим трем свойствам: атомарность, порядок и завершение.

Задача 1 (атомарная широковещательная рассылка)

Дано: поток сообщений, рассылаемых n параллельными процессорами, некоторые из которых могут быть сбойными.

Требуется: обеспечить последовательную доставку сообщений со следующими свойствами:

1. Атомарность: если любой исправный процессор доставляет обновление в момент времени U на своих часах, то это обновление было инициировано некоторым процессором и доставляется каждым исправным процессором в момент времени U на его часах.

2. Порядок: все обновления, доставляемые исправными процессорами, доставляются в том же порядке каждым исправным процессором.

3. Завершение: каждое обновление, широковещательная рассылка которого инициирована исправным процессором в момент времени T на его часах, доставляется всем исправным процессорам в момент времени T + [math]\displaystyle{ \Delta }[/math] на их часах.

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

Задача 2 (широковещательная рассылка полного порядка)

Дано: поток сообщений, рассылаемых n параллельными процессорами, некоторые из которых могут быть сбойными.

Требуется: обеспечить последовательную доставку сообщений со следующими свойствами:

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

2. Равномерная согласованность: если процессор доставляет сообщение m, то все исправные процессоры в конечном итоге доставляют m.

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

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

Основные результаты

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

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

Атомарная широковещательная рассылка при сбоях типа «пропуск»

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

(1) [math]\displaystyle{ \Delta_0 = \pi \delta + d \delta + \varepsilon }[/math].

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

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

Атомарная широковещательная рассылка при сбоях типа «ошибка синхронизации»

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

(2) [math]\displaystyle{ T - h \varepsilon \lt U \lt T + h(\delta + \varepsilon) }[/math].

Перед передачей сообщения каждый процессор проводит вышеприведенную проверку на приемлемость и отбрасывает сообщение, если оно не удовлетворяет данному условию. Время завершения [math]\displaystyle{ \Delta_t }[/math] протокола для случая ошибок синхронизации выглядит следующим образом:

(3) [math]\displaystyle{ \Delta_t = \pi (\delta + \varepsilon) + d \delta + \varepsilon }[/math].

Стоит отметить, что отбрасывание более ранних сообщений не является необходимым условием корректности, но гарантирует, что исправные процессоры хранят сообщения в своем журнале в течение ограниченного времени.

Атомарная широковещательная рассылка при сбоях типа «византийская ошибка»

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

[math]\displaystyle{ (relayed,... (relayed, (first, T, \sigma, p_1, s_1), p_2, s_2), ..., p_k, s_k) }[/math].

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

(4) [math]\displaystyle{ \Delta_b = \pi (\delta + \varepsilon) + d \delta + \varepsilon }[/math].

Однако в этом случае время передачи [math]\displaystyle{ \delta }[/math] должно быть значительно больше, чем в предыдущем, поскольку оно должно учитывать время, затрачиваемое на генерацию и проверку цифровых подписей, что обычно является дорогостоящей операцией.

Границы

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

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

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

Применение

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

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

Атомарная широковещательная рассылка использовалась для поддержки репликации запущенных процессов в системах реального времени или, если переформулировать задачу так, чтобы изолировать явные требования по синхронизации, также применялась для поддержки отказоустойчивости и репликации во многих инструментах групповой коммуникации (см. обзор Чоклера и др. [4]).

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

См. также

• Невозможность асинхронного консенсуса
• Причинно-следственное упорядочение, логические часы, репликация конечного автомата
• Синхронизация часов
• Детекторы отказов

Литература

1. Carr, R.: The Tandem global update protocol. Tandem Syst. Rev. 1,74-85(1985)

2. Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43,225-267 (1996)

3. Chang, J.-M., Maxemchuk, N.F.: Reliable broadcast protocols. ACM Trans. Comput. Syst. 2,251-273 (1984)

4. Chockler, G., Keidar, I., Vitenberg, R.: Group communication specifications: A comprehensive study. ACM Comput. Surv. 33, 427^69(2001)

5. Cristian, F.: Synchronous atomic broadcast for redundant broadcast channels. Real-Time Syst. 2,195-212 (1990)

6. Cristian, F., Aghili, H., Strong, R., Dolev, D.: Atomic Broadcast: From simple message diffusion to Byzantine agreement. In: Proc. 15th Intl. Symp. on Fault-Tolerant Computing (FTCS-15), Ann Arbor, June 1985 pp. 200-206. IEEE Computer Society Press

7. Cristian, F., Aghili, H., Strong, R., Dolev, D.: Atomic broadcast: From simple message diffusion to Byzantine agreement. In form. Comput. 118,158-179 (1995)

8. Defago, X., Schiper, A., Urban, P.: Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surveys 36,372-421 (2004)

9. Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32, 374-382(1985)

10. Hadzilacos, V., Toueg, S.: Fault-tolerant broadcasts and related problems. In: Mullender, S. (ed.) Distributed Systems, 2nd edn., pp. 97-146. ACM Press Books, Addison-Wesley (1993). Extended version appeared as Cornell Univ. TR 94-1425

11. Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Comm. ACM 21, 558-565 (1978)

12. Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Prog. Lang. Syst. 4, 382^01 (1982)

13. Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surveys 22, 299-319(1990)

14. Segall, A.: Distributed network protocols. IEEE Trans. Inform. Theory 29, 23-35(1983)

15. Wiesmann, M., Schiper, A.: Comparison of database replication techniques based on total order broadcast. IEEE Trans. Knowl. Data Eng. 17, 551-566 (2005)