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

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

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

Более конкретно, детектор сбоев – это функция D, которая ассоциирует с каждой моделью сбоев F множество историй детектора сбоев fHi g = D(F). И модель отказа, и история детектора сбоев сами являются функциями.

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

• История детектора сбоев H также является функцией, которая связывает с каждым процессом p и временем t некоторое значение v из диапазона значений детектора сбоев. (Диапазон детектора сбоев D обозначается RD). Считается, что это значение v было выдано детектором сбоев D для процесса p в момент времени t.

1. Идеальный детектор сбоев выдает подмножество процессов, т. е. диапазон детектора сбоев представляет собой множество подмножеств процессов в системе. Когда процесс q выводится в некоторое время t процессом p, то говорят, что q обнаружен (как аварийно завершенный) процессом p. Идеальный детектор сбоев гарантирует два следующих свойства:

• Каждый процесс, претерпевший аварийное завершение, в конечном итоге обязательно обнаруживается;

2. Эвентуально сильный детектор сбоев выдает подмножество процессов. Когда процесс q выводится в некоторое время t процессом p, то говорят, что q подозревается (в наличии аварийного завершения) процессом p. Эвентуально сильный детектор сбоев гарантирует два следующих свойства:

• Каждый процесс, претерпевший аварийное завершение, в конечном итоге подпадает под подозрение;

Идеальный детектор сбоев надежен: если процесс q обнаружен, значит, он аварийно завершен. Эвентуально сильный детектор сбоев ненадежен: у нас никогда нет гарантии, что выданный результат точен. Использование термина «подозрение» передает эту идею. Различие между ненадежностью и надежностью было точно отражено в работе [14] для общего контекста, когда диапазон детектора сбоев может быть произвольным.

'''Теорема 1 (Чандра-Туэг [ ]). Существует алгоритм, который решает задачу нахождения консенсуса с помощью идеального детектора сбоев.'''