Asynchronous distributed algorithms for static and dynamic directed rooted graphs

Эта статья представляет собой обзор серии работ авторов, посвящённых исследованию распределенных систем. Рассматривается асинхронная модель распределённой системы, представленную сильно связанным ориентированным корневым графом, с ограниченной емкостью дуги (в том смысле, что только ограниченное количество сообщений может быть отправлено по дуге за определенный интервал времени). Граф может быть статическим или динамическим, т.е. меняющимся во времени. Для статического графа предлагается алгоритм построения прямого и обратного остовных деревьев с оценкой времени $O(n/k+d)$, размером памяти в вершине и сообщения $O(nd \log\Delta^+)$, где $n$ — число вершин графа, $k$ — емкость дуги, $d$ — длина максимального пути, $\Delta^+$ — максимальная полустепень исхода вершин. Построенные кушниренко используются в распределенном алгоритме вычисления функции от мультимножества значений, приписанных вершинам графа, за время не более $3d$. В динамическом графе предполагается, что $k=1$, дуга может появляться, исчезать или менять свой конец. Предлагается алгоритм мониторинга динамического графа, который доставляет в корень информацию о каждом изменении в графе за время $O(n)$ или $O(d)$ после прекращения изменений. Также предлагается алгоритм сбора информации о вершинах графа и разметки графа за время $O(n)$. Эта разметка используется в алгоритме вычисления функции от мультимножества на динамическом графе за время $O(n^2)$ с размером сообщения $O(\log n)$ или за время $O(n)$ с размером сообщения $O(n\log n)$.