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

Фундаментальным результатом распределенных вычислений является невозможность разработки детерминированного алгоритма, решающего задачу согласования k множеств в асинхронных системах в случае <math>k \le t</math> [1, 7, 15]. По сравнению с невозможностью решения задачи асинхронного консенсуса, несмотря на аварийное завершение одного процесса, эта невозможность основана на углубленных комбинаторных соображениях. Эта невозможность открыла новые направления в исследовании связи между распределенными вычислениями и топологией. Топологический подход позволил выявить связи, увязывающие асинхронное согласование k множеств с другими задачами распределенных вычислений, такими как задача ''переименования'' [5].

Было исследовано несколько подходов для обхода упомянутой невозможности; эти подходы аналогичны тем, которые использовались для обхода невозможности асинхронного консенсуса, несмотря на аварийные завершения процесса.

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

Еще один исследованный подход включал комбинацию детекторов отказов и условий [8]. Условие представляет собой набор входных векторов, и каждый входной вектор содержит одну запись на процесс. Записи входного вектора, связанного с прогоном, содержат значения, предложенные процессами в этом прогоне. В принципе такой подход гарантирует, что безошибочные процессы всегда вычисляют решение в случаях, когда фактический входной вектор принадлежит условию, которым инстанциирован алгоритм согласования k множеств.