Алгоритм Дейкстры – Шолтена

Алгоритм Дейкстры – Шолтена (назван в честь Эдсгера В. Дейкстры и Карел С. Шолтен ) - это алгоритм для обнаружения завершения в распределенной системе. Алгоритм был предложен Дейкстрой и Шолтеном в 1980 году.

Сначала рассмотрим случай простого графа процессов, который является деревом. Распределенные вычисления с древовидной структурой не редкость. Такой граф процесса может возникнуть, когда вычисления строго относятся к типу разделяй и властвуй. Узел запускает вычисление и разделяет задачу на две (или более, обычно кратные 2) примерно равные части и распределяет эти части по другим процессорам. Этот процесс продолжается рекурсивно до тех пор, пока проблемы не станут достаточно маленькими, чтобы их можно было решить на одном процессоре.

• 1 Алгоритм
• 2 Алгоритм Дейкстры – Шолтена для дерева
• 3 Алгоритм Дейкстры – Шолтена для ориентированных ациклических графов
• 4 Алгоритм Дейкстры – Шолтена для циклических ориентированных графов
• 5 См. Также
• 6 Ссылки

Алгоритм Дейкстры – Шолтена - это древовидный алгоритм, который можно описать следующим образом:

• Инициатором вычисления является корень дерева.
• При получении вычислительного сообщения:
  • Если принимающий процесс в настоящее время не находится в вычислении: процесс присоединяется к дереву, становясь потомком отправителя сообщения. (На этом этапе сообщение подтверждения не отправляется.)
  • Если принимающий процесс уже находится в вычислении: процесс немедленно отправляет сообщение подтверждения отправителю сообщения.
• Когда у процесса больше нет дочерних элементов и стал бездействующим, процесс отсоединяется от дерева, отправляя сообщение подтверждения своему родительскому дереву.
• Завершение происходит, когда инициатор не имеет дочерних элементов и перешел в режим ожидания.

• Для дерева легко обнаружить завершение. Когда листовой процесс определяет, что он завершен, он отправляет сигнал своему родителю. В общем, процесс ожидает, пока все его дочерние элементы отправят сигналы, а затем он отправляет сигнал своему родителю.
• Программа завершается, когда корень получает сигналы от всех своих дочерних элементов.

• Алгоритм построения дерева может быть расширен до ациклических ориентированных графов. Мы добавляем дополнительный целочисленный атрибут Дефицит к каждому краю.
• На входящем фронте Дефицит будет обозначать разницу между количеством полученных сообщений и количеством сигналов, отправленных в ответ.
• Когда узел желает завершить работу, он ждет, пока не получит сигналы от исходящих ребер, уменьшая их дефицит до нуля.
• Затем он отправляет достаточно сигналов, чтобы гарантировать, что дефицит равен нулю на каждом входящем ребре.
• Поскольку граф является ациклическим, некоторые узлы не будут иметь исходящих ребер, и эти узлы будут первыми, которые завершатся после отправки достаточного количества сигналов своим входящим ребрам. После этого узлы на более высоких уровнях будут завершаться уровень за уровнем.

• Если циклы разрешены, предыдущий алгоритм не работает. Это потому, что не может быть ни одного узла с нулевыми исходящими ребрами. Таким образом, потенциально нет узла, который мог бы завершиться без консультации с другими узлами.
• Алгоритм Дейкстры – Шолтена решает эту проблему, неявно создавая связующее дерево графа. Покровное дерево - это дерево, которое включает в себя каждый узел базового графа один раз, а набор ребер является подмножеством исходного набора ребер.
• Дерево будет направленным (т. Е. Каналы будут направленными) с исходным узлом (который инициирует вычисление) в качестве корня.
• Spanning-tree создается следующим образом. К каждому узлу добавляется переменная First_Edge. Когда узел получает сообщение в первый раз, он инициализирует First_Edge тем ребром, через которое он получил сообщение. Впоследствии First_Edge никогда не изменяется. Обратите внимание, что связующее дерево не является уникальным и зависит от порядка сообщений в системе.
• Завершение обрабатывается каждым узлом в три этапа:
  1. Отправка сигналов на всех входящих ребрах, кроме первый край. (Каждый узел будет отправлять сигналы, которые уменьшают дефицит на каждом входящем фронте до нуля.)
  2. Дождитесь сигналов от всех исходящих фронтов. (Количество сигналов, полученных на каждом исходящем фронте, должно уменьшить каждый из их дефицитов до нуля.)
  3. Отправлять сигналы на First_Edge. (После выполнения шагов 1 и 2 узел сообщает своему родителю в связующем дереве о своем намерении завершить работу.)

• алгоритм Хуанга