Согласование множеств: различия между версиями

Один из подходов заключается в замене детерминированного алгоритма на рандомизированный. В этом случае свойство завершения формулируется следующим образом: «вероятность вычисления решения правильным процессом стремится к 1, когда число раундов стремится к <math>+ \infty</math>». Этот подход рассматривался в работе [9].

Также был предложен другой подход, основанный на детекторах сбоев. Грубо говоря, детектор сбоев предоставляет каждому процессу список процессов, которые предположительно были аварийно завершены. В качестве примера можно привести класс детекторов сбоев, обозначаемый <math>\Diamond S_x</math>, который включает все детекторы сбоев, такие, что через некоторое конечное (но неизвестное) время (1) любой список содержит аварийно завершенные процессы и (2) существует множество Q из x процессов, такое, что Q содержит один правильный процесс, и этот правильный процесс больше не подозревается процессами из Q (заметим, что правильные процессы могут подозреваться периодически или даже всегда). Строгие границы для задачи о согласовании k множеств в асинхронных системах с такими детекторами сбоев, предположенные в [9], были доказаны в [6]. Более точно, такой класс детекторов сбоев позволяет решить задачу согласования k множеств для <math>k \ge t - x + 2</math> [9] и не может решить ее при <math>k < t - x + 2</math> [6].