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

В [13] было показано, что для заданной степени координации k значение <math>t < \frac{k}{k+1} n</math> является верхней границей числа отказов процессов в случае, когда требуется решить задачу о согласовании k наборов в синхронной системе, подверженной отказам из-за любого пропуска. Алгоритм согласования k множеств, реализующий эту границу, был описан в работе [13]. Этот алгоритм требует, чтобы процессы выполнили R = t + 2 - k раундов перед вычислением решения. Доказательство (или опровержение) того, что R является нижней границей, когда <math>t < \frac{k}{k+1} n</math>, по-прежнему является открытым вопросом. Еще одной нерешенной задачей является разработка алгоритма согласования k множеств с ранним вычислением решений для <math>t < \frac{k}{k+1} n</math> и k > 1.

Также был предложен другой подход, основанный на детекторах отказов. Грубо говоря, детектор отказов предоставляет каждому процессу список процессов, которые предположительно были аварийно завершены. В качестве примера можно привести класс детекторов отказов, обозначаемый <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].