4551
правка
Детекторы сбоев: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
Более конкретно, детектор сбоев – это функция D, которая ассоциирует с каждой ''моделью сбоев' F множество ''историй детектора сбоев'' <math> \{ H_i \} = D(F)</math>. И модель отказа, и история детектора сбоев сами являются функциями. | Более конкретно, детектор сбоев – это функция D, которая ассоциирует с каждой ''моделью сбоев'' F множество ''историй детектора сбоев'' <math> \{ H_i \} = D(F)</math>. И модель отказа, и история детектора сбоев сами являются функциями. | ||
• Модель сбоев F – это функция, связывающая с каждым временем t множество процессов F(t), переживших аварийное завершение к моменту t. Это понятие предполагает существование глобальных часов, не зависящих от процессов, а также конкретное понятие события ''аварийного завершения', связанное со временем. Множество моделей сбоев называется ''средой''. | • Модель сбоев F – это функция, связывающая с каждым временем t множество процессов F(t), переживших аварийное завершение к моменту t. Это понятие предполагает существование глобальных часов, не зависящих от процессов, а также конкретное понятие события ''аварийного завершения', связанное со временем. Множество моделей сбоев называется ''средой''. | ||
| Строка 67: | Строка 67: | ||
Данная теорема неявно говорит о том, что если распределенная система предоставляет средства для реализации идеального обнаружения сбоев, то невозможность консенсуса можно обойти, даже если все процессы, кроме одного, завершаются аварийно. Фактически этот результат справедлив для любой модели сбоя, то есть в любой среде | Данная теорема неявно говорит о том, что если распределенная система предоставляет средства для реализации идеального обнаружения сбоев, то невозможность консенсуса можно обойти, даже если все процессы, кроме одного, завершаются аварийно. Фактически этот результат справедлив для любой модели сбоя, то есть в любой среде. | ||
Вторая теорема, приведенная ниже, связывает существование алгоритма консенсуса с предположением об устойчивости. Говоря более конкретно, данная теорема справедлива в ''мажоритарной'' среде, которая представляет собой множество моделей сбоев, где более половины процессов исправны. | |||
Алгоритм, лежащий в основе приведенного выше результата, похож на алгоритмы эвентуально синхронного консенсуса [10], а также имеет некоторое сходство с алгоритмом Паксос [18]. | '''Теорема 2 (Чандра-Туэг [5]). Существует алгоритм, который решает задачу консенсуса с помощью эвентуально сильного детектора сбоев в мажоритарной среде.''' | ||
Алгоритм, лежащий в основе приведенного выше результата, похож на алгоритмы ''эвентуально синхронного'' консенсуса [10], а также имеет некоторое сходство с алгоритмом Паксос [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D0%B0%D0%BA%D1%81%D0%BE%D1%81] [18]. | |||
В работе [5] было показано, что ни один алгоритм, использующий только | В работе [5] было показано, что ни один алгоритм, использующий только эвентуально сильный детектор сбоев, не может решить задачу консенсуса без предположения о большинстве. (В [14] этот результат обобщен на любой ненадежный детектор сбоев). Эта нижняя граница устойчивости интуитивно объясняется возможностью наличия разбиений в системе передачи сообщений, где по крайней мере половина процессов может завершиться аварийно, а детектор сбоев ненадежен. Скажем, в разделяемой памяти такой возможности нет, и задача консенсуса может быть решена с помощью ''эвентуально сильного'' детектора сбоев [19]. | ||
'''Редукции детекторов сбоев''' | '''Редукции детекторов сбоев''' | ||
Детекторы сбоев можно сравнивать друг с другом. Считается, что детектор сбоев <math>D_2</math> слабее детектора сбоев <math>D_1</math>, если существует асинхронный алгоритм, называемый алгоритмом ''редукции'', который может эмулировать <math>D_2</math>, используя <math>D_1</math>. Здесь важно сделать три замечания. | |||
• То, что алгоритм редукции является асинхронным, означает, что он не использует никакого другого источника информации о сбоях, кроме <math>D_1</math>. | |||
• То, что алгоритм редукции является асинхронным, означает, что он не использует никакого другого источника информации о сбоях, кроме | |||
• Эмуляция детектора сбоев | • Эмуляция детектора сбоев <math>D_2</math> означает реализацию распределенной переменной, которая имитирует выходной результат, который мог бы предоставить <math>D_2</math>. | ||
• Существование алгоритма редукции зависит от среды. Поэтому, строго говоря, тот факт, что один детектор сбоев слабее другого, зависит от рассматриваемой среды. | • Существование алгоритма редукции зависит от среды. Поэтому, строго говоря, тот факт, что один детектор сбоев слабее другого, зависит от рассматриваемой среды. | ||
Если детектор сбоев | Если детектор сбоев <math>D_1</math> слабее <math>D_2</math> и наоборот, то считается, что <math>D_1</math> и <math>D_2</math> ''эквивалентны''. В противном случае, если <math>D_1</math> слабее <math>D_2</math>, а <math>D_2</math> не слабее <math>D_1</math>, то говорят, что <math>D_1</math> ''строго слабее'' <math>D_2</math>. Опять же, строго говоря, эти понятия зависят от рассматриваемой среды. | ||
Возможность сравнивать детекторы сбоев помогает определить понятие самого слабого детектора сбоев для решения этой задачи. Детектор сбоев D является самым слабым для решения задачи P, если выполняются два следующих условия: | Возможность сравнивать детекторы сбоев помогает определить понятие ''самого слабого'' детектора сбоев для решения этой задачи. Детектор сбоев D является самым слабым для решения задачи P, если выполняются два следующих условия: | ||
• Существует алгоритм, который решает задачу P с помощью детектора D. | • Существует алгоритм, который решает задачу P с помощью детектора D. | ||
• Если существует алгоритм, который решает P с помощью некоторого детектора сбоев | • Если существует алгоритм, который решает P с помощью некоторого детектора сбоев D', то D слабее, чем D'. | ||
'''Теорема 3 (Чандра-Хадзилакос-Туэг [ ]). Эвентуально сильный детектор сбоев является самым слабым для решения задачи консенсуса в мажоритарной среде.''' | '''Теорема 3 (Чандра-Хадзилакос-Туэг [4]). Эвентуально сильный детектор сбоев является самым слабым для решения задачи консенсуса в мажоритарной среде.''' | ||
