Алгоритм Дейкстры – Шолтена - Dijkstra–Scholten algorithm - Wikipedia

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

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

Алгоритм

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

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

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

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

Алгоритм Дейкстры – Шолтена для ориентированных ациклических графов

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

Алгоритм Дейкстры – Шолтена для циклических ориентированных графов

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

Смотрите также

Рекомендации

  1. ^ Гош, Сукумар (2010), «9.3.1 Алгоритм Дейкстры – Шолтена», Распределенные системы: алгоритмический подход, CRC Press, стр. 140–143, ISBN  9781420010848.
  2. ^ Фоккинк, Ван (2013), «6.1 Алгоритм Дейкстры – Шолтена», Распределенные алгоритмы: интуитивный подход, MIT Press, стр. 38–39, ISBN  9780262318952.
  3. ^ Dijkstra, Edsger W .; Шолтен, С. С. (1980), «Обнаружение завершения для рассеивающих вычислений» (PDF), Письма об обработке информации, 11 (1): 1–4, Дои:10.1016/0020-0190(80)90021-6, МИСТЕР  0585394.