Детекторы сбоев: различия между версиями

Частичная синхронность; тайм-ауты; информация о сбоях; распределенные оракулы

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

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

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

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

• Модель сбоев F – это функция, связывающая с каждым временем t множество процессов F(t), переживших аварийное завершение к моменту t. Это понятие предполагает существование глобальных часов, не зависящих от процессов, а также конкретное понятие события ''аварийного завершения', связанное со временем. Множество моделей сбоев называется ''средой''.

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

Вторая теорема, приведенная ниже, связывает существование алгоритма консенсуса с предположением об устойчивости. Говоря более конкретно, данная теорема справедлива в ''мажоритарной'' среде, которая представляет собой множество моделей сбоев, где более половины процессов исправны.

Детекторы сбоев можно сравнивать друг с другом. Считается, что детектор сбоев <math>D_2</math> слабее детектора сбоев <math>D_1</math>, если существует асинхронный алгоритм, называемый алгоритмом ''редукции'', который может эмулировать <math>D_2</math>, используя <math>D_1</math>. Здесь важно сделать три замечания.

Определение концепции детектора сбоев оказало положительное влияние на проектирование надежных распределенных архитектур.

Второе применение концепции детекторов сбоев – это теория распределенной вычислимости. Детекторы сбоев позволяют классифицировать задачи. Задача A ''сложнее'' (или ''строго сложнее'') задачи B, если самый слабый детектор сбоев для решения B слабее (или строго слабее) самого слабого детектора сбоев для решения A. (Это понятие, конечно, параметризуется конкретгной средой).

Может показаться удивительным, что индуцированная редукция детекции сбоев между разными задачами не вполне соответствует классическому понятию редукции к ''«черному ящику»''. Например, хорошо известно, что не существует асинхронного распределенного алгоритма, который мог бы использовать абстракцию ''очереди'' (Queue) для реализации абстракции ''сравнения с обменом'' (Compare-Swap) в системе из n > 2 процессов, где n – 1 процессов могут претерпеть сбой в виде аварийного завершения [15]. В этом смысле абстракция сравнения с обменом строго более мощная (в смысле «черного ящика»), чем абстракция очереди. Имеет место следующий результат:

'''Теорема 4 (Дельпорт-Фоконье-Геррауи [9]). Самый слабый детектор сбоев для решения задачи очереди также является самым слабым для решения задачи сравнения с обменом в системе из n > 2 процессов, где n – 1 процессов могут претерпеть сбой в виде аварийного завершения.'''

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

Некоторые проблемы, лежащие в основе концепции детектора сбоев, все еще остаются нерешенными. Одна из таких проблем заключается в определении самого слабого детектора сбоев для решения фундаментальной задачи [[Согласование множеств|согласования множеств]] [6]: это задача на принятие решений, в которой процессы должны согласовать до k значений, а не одно значение, как в случае задачи консенсуса. Три независимые группы исследователей [3, 16, 22] доказали невозможность решения этой задачи в асинхронной системе с k сбоями, обобщив невозможность консенсуса [13]. Определение самого слабого детектора сбоев, позволяющего обойти эту невозможность, несомненно, поможет понять основы сводимости детекции сбоев.