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

 

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

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

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