Алгоритм Дейкстры и Шолтена
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Алгоритм Дейкстры и Шолтена[1] решает задачу останова диффундирующего вычисления в распределённой системе.
Основная идея: выстроить процессы в дерево: кто кого активизировал. Процесс добавляется в дерево (становится "красным"), когда становится активным, а удаляется (становится "зелёным"), когда он и все его потомки стали пассивными и там нет сообщений (т.е. поддерево закончило вычисления). Исходно дерево содержит только инициатора, а когда вычисление остановится, станет пустым (о чём узнает инициатор).
Каждый процесс будет требовать подтверждения на каждое своё сообщение, чтобы можно было учесть сообщения в пути.
Каждый процесс хранит внутри себя несколько чисел:
- Количество неподтверждённых сообщений остальным процессам. Увеличивается при отправке сообщения, кроме ack. Уменьшается при получении ack (у нас всё ещё не бывает ошибок и перепосылок, они дальше в билетах).
- Количество детей в дереве.
- Номер родительского процесса (null для инициатора, он же корень).
Процесс называется зелёным, если выполняются все следующие условия:
- Процесс пассивен (в смысле диффундирующего вычисления, в нашем алгоритме он всё ещё может общаться с остальными)
- Нет неподтверждённых сообщений другим процессам
- У него нет детей в дереве
В противном случае процесс называется красным. Дерево состоит в точности из множества красных процессов. Чтобы поддерживать этот инвариант, требуется задать поведение процессов:
- Зелёный процесс не отправляет никому сообщения
- Зелёный процесс остаётся зелёным, пока не получит сообщение (это не может быть ack, и это сообщение только от красного):
- При получении становится красным и новым листом в дереве
- Отсылает автору сообщения сообщения "я твой новый ребёнок", после чего автор увеличивает количество своих детей
- Красный процесс может отправить сообщение другому красному, тогда никаких изменений состояния не происходит (только меняется счётчик неподтверждённых сообщений у отправителя)
- Красный процесс остаётся красным, пока не начинают выполняться условия для становления зелёным:
- Если процесс стал зелёным, он удаляет себя из дерева, послав родителю сообщения "я больше не твой ребёнок", после чего родитель уменьшает количество своих детей
Тогда диффундирующее вычисление заканчивается в точности когда корень дерева (инициатор) становится зелёным.
Итого у нас получается $N$ процессов и $m$ сообщений в сумме требуется послать $2m+k\le 3m$ сообщений(?), где $k$ — количество раз, которые вершина становится красной:
- На каждое из $m$ сообщение идёт ответ: либо с пометкой "я твой новый ребёнок", либо без пометки.
- Каждый раз, когда вершина становится красной, она должна в какой-то момент стать обратно зелёной и отправить родителю оповещение.
