Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм Дайкстры — Шольтена (названный в честь Эдсгера В. Дайкстры и Карела С. Шольтена) — это алгоритм для обнаружения завершения в распределенной системе. Алгоритм был предложен Дайкстрой и Шольтеном в 1980 году. Сначала рассмотрим случай простого графа процессов, который представляет собой дерево. Распределенные вычисления, имеющие древовидную структуру, не являются редкостью. Такой граф процессов может возникнуть, когда вычисление представляет собой строгое разделение и объединение. Узел начинает вычисление и разделяет задачу на две (или более, обычно кратное 2) примерно равные части и распределяет эти части другим процессорам. Этот процесс продолжается рекурсивно, пока задачи не станут достаточно малыми для решения на одном процессоре.
The Dijkstra–Scholten algorithm (named after Edsger W. Dijkstra and Carel S. Scholten) is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Dijkstra and Scholten in 1980. First, consider the case of a simple process graph which is a tree. A distributed computation which is tree structured is not uncommon. Such a process graph may arise when the computation is strictly a divide and conquer type. A node starts the computation and divides the problem in two (or more, usually a multiple of 2) roughly equal parts and distribute those parts to other processors. This process continues recursively until the problems are of sufficiently small size to solve in a single processor.
Алгоритм DijkstraScholten для дерева
Для дерева легко определить завершение работы. Когда дочерний процесс (лист) определяет, что он завершил работу, он посылает сигнал своему родительскому процессу. В общем случае, процесс ожидает получения сигналов от всех своих дочерних процессов, а затем посылает сигнал своему родительскому процессу. Программа завершается, когда корневой процесс получает сигналы от всех своих дочерних процессов.
For a tree, it is easy to detect termination. When a leaf process determines that it has terminated, it sends a signal to its parent. In general, a process waits for all its children to send signals and then it sends a signal to its parent. The program terminates when the root receives signals from all its children.
Алгоритм Дийкстра-Шолтена для направленных ациклических графов
Алгоритм для дерева может быть расширен на ациклические ориентированные графы. Мы добавляем к каждому ребру дополнительный целочисленный атрибут – Дефицит. На входящем ребре Дефицит будет обозначать разницу между количеством полученных сообщений и количеством отправленных в ответ сигналов. Когда узел хочет завершить работу, он ждет, пока не получит сигналы от исходящих ребер, уменьшающие их дефицит до нуля. Затем он отправляет достаточно сигналов, чтобы обеспечить нулевой дефицит на каждом входящем ребре. Поскольку граф ацикличен, некоторые узлы не будут иметь исходящих ребер, и эти узлы завершат работу первыми после отправки достаточного количества сигналов на их входящие ребра. После этого узлы на более высоких уровнях будут завершать работу уровень за уровнем.
The algorithm for a tree can be extended to acyclic directed graphs. We add an additional integer attribute Deficit to each edge. On an incoming edge, Deficit will denote the difference between the number of messages received and the number of signals sent in reply. When a node wishes to terminate, it waits until it has received signals from outgoing edges reducing their deficits to zero. Then it sends enough signals to ensure that the deficit is zero on each incoming edge. Since the graph is acyclic, some nodes will have no outgoing edges and these nodes will be the first to terminate after sending enough signals to their incoming edges. After that the nodes at higher levels will terminate level by level.