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

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