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

Отказы случаются, однако на практике они редки. Обозначим за 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].