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

Задача согласования k множеств всегда может быть решена в синхронной системе. Основной результат заключается в определении минимального числа раундов (<math>R_t</math>), необходимых для вычислений с помощью безошибочных процессов в наихудшем сценарии (такой сценарий имеет место, когда в каждом раунде ровно k процессов приходят к аварийному завершению). В работе [3] было показано, что <math>R_t = \lfloor \frac{t}{k} \rfloor + 1</math>. Очень простой алгоритм, реализующий эту нижнюю границу, изображен на рис. 1.

  (4)      ''отправить'' <math>(est_i)</math> ''всем''; % включая сам <math>p_i</math> %

  (5)      <math>est_i \gets min( \{ </math> значения <math>(est_i)</math>, полученные в ходе текущего раунда r});

Отказы случаются, однако на практике они редки. Обозначим за f количество процессов, приводящих к аварийному завершению в данном прогоне алгоритма, <math>0 \le f \le t</math>. Нас интересуют синхронные алгоритмы, которые завершаются максимум за <math>R_t</math> раундов в случае, когда на текущем прогоне аварийно завершаются t процессов, но которые позволяют безошибочным процессам выполнить вычисление за гораздо меньшее число раундов, если отказов мало. Такие алгоритмы называются ''алгоритмами с ранним принятием решений''. В [4] было показано, что при наличии f аварийных завершений процессов любой алгоритм согласования k множеств с ранним принятием решений имеет прогоны, на которых ни один процесс не принимает решение до раунда <math>R_f = min(\lfloor \frac{f}{k} \rfloor + 2, \lfloor \frac{t}{k} \rfloor + 1)</math>. Эта нижняя граница показывает неизбежно присущий им компромисс, устанавливающий связь между степенью координации k, максимальным количеством отказов процесса t, фактическим количеством отказов процесса f и наилучшей достижимой временной сложностью. Алгоритмы согласования k множеств с ранним принятием решений для синхронной модели можно найти в [4, 12].

Алгоритм согласования 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> раундов.

В [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.