4551
правка
Согласование множеств: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 32: | Строка 32: | ||
== Основные результаты == | == Основные результаты == | ||
Задача согласования k множеств всегда может быть решена в синхронной системе. Основной результат заключается в определении минимального числа раундов (<math>R_t</math>), необходимых для вычислений с помощью безошибочных процессов в наихудшем сценарии (такой сценарий имеет место, когда в каждом раунде ровно k процессов приходят к аварийному завершению). В работе [3] было показано, что <math>R_t = \ | Задача согласования k множеств всегда может быть решена в синхронной системе. Основной результат заключается в определении минимального числа раундов (<math>R_t</math>), необходимых для вычислений с помощью безошибочных процессов в наихудшем сценарии (такой сценарий имеет место, когда в каждом раунде ровно k процессов приходят к аварийному завершению). В работе [3] было показано, что <math>R_t = \lfloor \frac{t}{k} \rfloor + 1</math>. Очень простой алгоритм, реализующий эту нижнюю границу, изображен на рис. 1. | ||
'''Function''' k-set_agreement (<math>v_i</math>) | |||
(1) <math>est_i \gets v_i;</math> | |||
(2) '''when''' <math>r = 1, 2, ..., \lfloor \frac{t}{k} \rfloor + 1</math> '''do''' % r: округлить число % | |||
(3) '''begin_round''' | |||
(4) ''отправить'' <math>(est_i)</math> ''всем''; % включая сам <nath>p_i</math> % | |||
(5) <math>est_i \gets min( \{ </math> значения <math>(est_i)</math>, полученные в ходе текущего раунда r}); | |||
(6) '''end_round'''; | |||
(7) ''возврат'' <math>(est_i)</math> | |||
Рисунок 1. | Рисунок 1. | ||
Простой синхронный алгоритм согласования k множеств (код для | Простой синхронный алгоритм согласования k множеств (код для <math>(p_i)</math>) | ||