4551
правка
Согласование множеств: различия между версиями
Материал из WEGA
м
нет описания правки
Irina (обсуждение | вклад) м (→Определение) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 30: | Строка 30: | ||
В этой модели вычислений каждое выполнение представляет собой последовательность раундов. Они обозначаются последовательными целыми числами – 1, 2 и т.д. Для процессов номер текущего раунда представляется в виде глобальной переменной, глобальное увеличение которой влечет за собой их собственный локальный прогресс. Во время раунда процесс сначала передает сообщение, затем получает сообщения и, наконец, выполняет локальные вычисления. Фундаментальное свойство синхронности, которое обеспечивает процессам синхронная система, заключается в следующем: сообщение, отправленное в раунде r, принимается процессом-получателем в том же раунде r. Если в текущем раунде процесс при отправке сообщения приходит к аварийному завершению, то это сообщение получает произвольное (не известное заранее) подмножество процессов. | В этой модели вычислений каждое выполнение представляет собой последовательность раундов. Они обозначаются последовательными целыми числами – 1, 2 и т.д. Для процессов номер текущего раунда представляется в виде глобальной переменной, глобальное увеличение которой влечет за собой их собственный локальный прогресс. Во время раунда процесс сначала передает сообщение, затем получает сообщения и, наконец, выполняет локальные вычисления. Фундаментальное свойство синхронности, которое обеспечивает процессам синхронная система, заключается в следующем: сообщение, отправленное в раунде r, принимается процессом-получателем в том же раунде r. Если в текущем раунде процесс при отправке сообщения приходит к аварийному завершению, то это сообщение получает произвольное (не известное заранее) подмножество процессов. | ||
== Основные результаты == | |||
Задача согласования k множеств всегда может быть решена в синхронной системе. Основной результат заключается в определении минимального числа раундов (<math>R_t</math>), необходимых для вычислений с помощью безошибочных процессов в наихудшем сценарии (такой сценарий имеет место, когда в каждом раунде ровно k процессов приходят к аварийному завершению). В работе [3] было показано, что <math>R_t = \langle \frac{t}{k} \rangle + 1</math>. Очень простой алгоритм, реализующий эту нижнюю границу, изображен на рис. 1. | |||
Рисунок 1. | Рисунок 1. | ||
Простой синхронный алгоритм согласования k множеств (код для pi) | Простой синхронный алгоритм согласования k множеств (код для pi) | ||
