Параллельные вычисления на динамически меняющемся графе

Рассматривается задача параллельного вычисления значения функции от мультимножества значений, записанных в вершинах ориентированного сильно-связного графа. Вычисление выполняется автоматами, находящимися в вершинах графа. Автомат имеет локальную информацию о графе: он «знает» только о дугах, выходящих из вершины, в которой он находится, но «не знает», куда (в какие вершины) эти дуги ведут. Автоматы обмениваются сообщениями, передаваемыми по дугам графа, которые играют роль каналов передачи сообщений. Вычисление инициируется сообщением, приходящим извне в автомат выделенной начальной вершины графа. Этот же автомат в конце работы посылает вовне вычисленное значение функции. Для решения этой задачи предлагаются два алгоритма. Первый алгоритм выполняет исследование графа, целью которого является разметка графа с помощью изменения состояний автоматов в вершинах. Такая разметка используется вторым алгоритмом, который и производит вычисление значения той или иной функции. Это вычисление основано на алгоритме пульсации: сначала от автомата начальной вершины по всему графу распространяются сообщения-вопросы , которые должны достигнуть каждой вершины, а затем от каждой вершины «в обратную сторону» к начальной вершине двигаются сообщения-ответы . Алгоритм пульсации, по сути, вычисляет агрегатные функции, для которых значение функции от объединения мультимножеств вычисляется по значениям функции от этих мультимножеств. Однако показано, что любая функция $F(x)$ имеет агрегатное расширение, то есть может быть вычислена как $H(G(x))$ , где $G$ агрегатная функция. Заметим, что разметка графа не зависит от той функции, которая будет вычисляться. Это означает, что разметка графа выполняется один раз, после чего может многократно использоваться для вычисления различных функций. Поскольку автоматы в вершинах графа работают параллельно, как разметка графа, так и вычисление функции выполняются параллельно. Это первая особенность работы. Вторая особенность — вычисления выполняются на динамически меняющемся графе: его дуги могут исчезать, появляться или менять свои конечные вершины. На изменения графа налагаются такие минимальные ограничения, которые позволяют решать эту задачу за ограниченное время. Приводится оценка времени работы обоих предлагаемых алгоритмов.