1632
правки
Изменения
м
rollbackEdits.php mass rollback
[[Категория: Параллельное программирование]]
Алгоритм Дейкстры и Шолтена<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref> решает задачу останова [[Диффундирующие вычисления|диффундирующего вычисления]] в распределённой системе.
** При получении становится красным и новым листом в дереве
** Отсылает автору сообщения сообщения "я твой новый ребёнок", после чего автор увеличивает количество своих детей
* Красный процесс может отправить сообщение другому красному, тогда никаких изменений состояния не происходит(только меняется счётчик неподтверждённых сообщений у отправителя)
* Красный процесс остаётся красным, пока не начинают выполняться условия для становления зелёным:
** Если процесс стал зелёным, он удаляет себя из дерева, послав родителю сообщения "я больше не твой ребёнок", после чего родитель уменьшает количество своих детей
Тогда диффундирующее вычисление заканчивается в точности когда корень дерева (инициатор) становится зелёным.
Итого у нас получается $N$ процессов и $m$ сообщений в сумме требуется послать $2m+k\le 3m$ сообщений(?), где $k$ — количество раз, которые вершина становится красной:
* На каждое из $m$ сообщение идёт ответ: либо с пометкой "я твой новый ребёнок", либо без пометки.
* Каждый раз, когда вершина становится красной, она должна в какой-то момент стать обратно зелёной и отправить родителю оповещение.
