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

Алгоритм согласования k множеств с ранним принятием решений для модели с отказом из-за любого пропуска был описан в [13]. Этот алгоритм, которому требуется t < n/2 времени, приводит хороший процесс к принятию решения и остановке максимум за <math>R_f = min(\lfloor \frac{f}{k} \rfloor + 2, \lfloor \frac{t}{k} \rfloor + 1)</math> раундов. При этом процесс, который не является хорошим, выполняется не более <math>R_f(not_ good) = min(\lceil \frac{f}{k} \rceil + 2, \lceil \frac{t}{k} \rceil + 1)</math> раундов.

Поскольку <math>R_f</math> является нижней границей для числа раундов в модели отказов с аварийным завершением, предыдущий алгоритм показывает, что это значение также является нижней границей для вычисления решения безошибочными процессами в более строгой модели с отказом из-за любого пропуска. Доказательство того, что <math>R_f(not_ good)</math> представляет собой верхнюю границу числа раундов, которые должен выполнить процесс, не являющийся хорошим, пока не найдено.

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

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

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