292
правки
Изменения
Новая страница: «Алгоритм Дейкстры и Шолтена<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref> решает задачу останова…»
Алгоритм Дейкстры и Шолтена<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref> решает задачу останова [[Диффундирующие вычисления|диффундирующего вычисления]] в распределённой системе.
Основная идея: выстроить процессы в дерево: кто кого активизировал. Процесс добавляется в дерево (становится "красным"), когда становится активным, а удаляется (становится "зелёным"), когда он и все его потомки стали пассивными и там нет сообщений (т.е. поддерево закончило вычисления). Исходно дерево содержит только инициатора, а когда вычисление остановится, станет пустым (о чём узнает инициатор).
Каждый процесс будет требовать подтверждения на каждое своё сообщение, чтобы можно было учесть сообщения в пути.
Каждый процесс хранит внутри себя несколько чисел:
# Количество неподтверждённых сообщений остальным процессам. Увеличивается при отправке сообщения, кроме ack. Уменьшается при получении ack (у нас всё ещё не бывает ошибок и перепосылок, они дальше в билетах).
# Количество детей в дереве.
# Номер родительского процесса (null для инициатора, он же корень).
Процесс называется ''зелёным'', если выполняются все следующие условия:
# Процесс пассивен (в смысле диффундирующего вычисления, в нашем алгоритме он всё ещё может общаться с остальными)
# Нет неподтверждённых сообщений другим процессам
# У него нет детей в дереве
В противном случае процесс называется ''красным''.
Дерево состоит в точности из множества красных процессов.
Чтобы поддерживать этот инвариант, требуется задать поведение процессов:
* Зелёный процесс не отправляет никому сообщения
* Зелёный процесс остаётся зелёным, пока не получит сообщение (это не может быть ack, и это сообщение только от красного):
** При получении становится красным и новым листом в дереве
** Отсылает автору сообщения сообщения "я твой новый ребёнок", после чего автор увеличивает количество своих детей
* Красный процесс может отправить сообщение другому красному, тогда никаких изменений состояния не происходит
* Красный процесс остаётся красным, пока не начинают выполняться условия для становления зелёным:
** Если процесс стал зелёным, он удаляет себя из дерева, послав родителю сообщения "я больше не твой ребёнок", после чего родитель уменьшает количество своих детей
Тогда диффундирующее вычисление заканчивается в точности когда корень дерева (инициатор) становится зелёным.
Основная идея: выстроить процессы в дерево: кто кого активизировал. Процесс добавляется в дерево (становится "красным"), когда становится активным, а удаляется (становится "зелёным"), когда он и все его потомки стали пассивными и там нет сообщений (т.е. поддерево закончило вычисления). Исходно дерево содержит только инициатора, а когда вычисление остановится, станет пустым (о чём узнает инициатор).
Каждый процесс будет требовать подтверждения на каждое своё сообщение, чтобы можно было учесть сообщения в пути.
Каждый процесс хранит внутри себя несколько чисел:
# Количество неподтверждённых сообщений остальным процессам. Увеличивается при отправке сообщения, кроме ack. Уменьшается при получении ack (у нас всё ещё не бывает ошибок и перепосылок, они дальше в билетах).
# Количество детей в дереве.
# Номер родительского процесса (null для инициатора, он же корень).
Процесс называется ''зелёным'', если выполняются все следующие условия:
# Процесс пассивен (в смысле диффундирующего вычисления, в нашем алгоритме он всё ещё может общаться с остальными)
# Нет неподтверждённых сообщений другим процессам
# У него нет детей в дереве
В противном случае процесс называется ''красным''.
Дерево состоит в точности из множества красных процессов.
Чтобы поддерживать этот инвариант, требуется задать поведение процессов:
* Зелёный процесс не отправляет никому сообщения
* Зелёный процесс остаётся зелёным, пока не получит сообщение (это не может быть ack, и это сообщение только от красного):
** При получении становится красным и новым листом в дереве
** Отсылает автору сообщения сообщения "я твой новый ребёнок", после чего автор увеличивает количество своих детей
* Красный процесс может отправить сообщение другому красному, тогда никаких изменений состояния не происходит
* Красный процесс остаётся красным, пока не начинают выполняться условия для становления зелёным:
** Если процесс стал зелёным, он удаляет себя из дерева, послав родителю сообщения "я больше не твой ребёнок", после чего родитель уменьшает количество своих детей
Тогда диффундирующее вычисление заканчивается в точности когда корень дерева (инициатор) становится зелёным.
