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

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

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