292
правки
Изменения
Нет описания правки
** При получении становится красным и новым листом в дереве
** Отсылает автору сообщения сообщения "я твой новый ребёнок", после чего автор увеличивает количество своих детей
* Красный процесс может отправить сообщение другому красному, тогда никаких изменений состояния не происходит(только меняется счётчик неподтверждённых сообщений у отправителя)
* Красный процесс остаётся красным, пока не начинают выполняться условия для становления зелёным:
** Если процесс стал зелёным, он удаляет себя из дерева, послав родителю сообщения "я больше не твой ребёнок", после чего родитель уменьшает количество своих детей
Тогда диффундирующее вычисление заканчивается в точности когда корень дерева (инициатор) становится зелёным.
Итого у нас получается $N$ процессов и $m$ сообщений в сумме требуется послать $2m+k\le 3m$ сообщений(?), где $k$ — количество раз, которые вершина становится красной:
* На каждое из $m$ сообщение идёт ответ: либо с пометкой "я твой новый ребёнок", либо без пометки.
* Каждый раз, когда вершина становится красной, она должна в какой-то момент стать обратно зелёной и отправить родителю оповещение.
