4551
правка
Согласование множеств: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
Задача согласования k множеств всегда может быть решена в синхронной системе. Основной результат заключается в определении минимального числа раундов (<math>R_t</math>), необходимых для вычислений с помощью безошибочных процессов в наихудшем сценарии (такой сценарий имеет место, когда в каждом раунде ровно k процессов приходят к аварийному завершению). В работе [3] было показано, что <math>R_t = \lfloor \frac{t}{k} \rfloor + 1</math>. Очень простой алгоритм, реализующий эту нижнюю границу, изображен на рис. 1. | Задача согласования 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>) | |||
'''Function''' k-set_agreement (<math>v_i</math>) | |||
(1) <math>est_i \gets 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: | (2) '''when''' <math>r = 1, 2, ..., \lfloor \frac{t}{k} \rfloor + 1</math> '''do''' % r: номер раунда % | ||
(3) '''begin_round''' | (3) '''begin_round''' | ||
(4) ''отправить'' <math>(est_i)</math> ''всем''; % включая сам <nath>p_i</math> % | (4) ''отправить'' <math>(est_i)</math> ''всем''; % включая сам <nath>p_i</math> % | ||
| Строка 48: | Строка 47: | ||
Отказы случаются, однако на практике они редки. Обозначим за f количество процессов, приводящих к аварийному завершению в данном прогоне алгоритма, 0 < f < t. Нас интересуют синхронные алгоритмы, которые завершаются максимум за | Отказы случаются, однако на практике они редки. Обозначим за f количество процессов, приводящих к аварийному завершению в данном прогоне алгоритма, 0 < f < t. Нас интересуют синхронные алгоритмы, которые завершаются максимум за <math>R_t</math> раундов в случае, когда на текущем прогоне аварийно завершаются t процессов, но которые позволяют безошибочным процессам выполнить вычисление за гораздо меньшее число раундов, если отказов мало. Такие алгоритмы называются алгоритмами с ранним принятием решений. В [ ] было показано, что при наличии f аварийных завершений процессов любой алгоритм согласования k множеств с ранним принятием решений имеет прогоны, на которых ни один процесс не принимает решение до раунда Rf = min(bkfc + 2; bktc + 1). Эта нижняя граница показывает неизбежно присущий им компромисс, устанавливающий связь между степенью координации k, максимальным количеством отказов процесса t, фактическим количеством отказов процесса f и наилучшей достижимой временной сложностью. Алгоритмы согласования k множеств с ранним принятием решений для синхронной модели можно найти в [4, 12]. | ||