Асинхронные распределенные алгоритмы на статических и динамических ориентированных корневых графахстатья

Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Дата последнего поиска статьи во внешних источниках: 6 декабря 2018 г.

Работа с статьей


[1] Асинхронные распределенные алгоритмы на статических и динамических ориентированных корневых графах / И. Б. Бурдонов, А. С. Косачев, В. В. Кулямин и др. // Труды Института системного программирования РАН (электронный журнал). — 2018. — Т. 30, № 1. — С. 69–88. Эта статья представляет собой обзор серии работ авторов, посвящённых исследованию распределенных систем. Рассматривается асинхронная модель распределённой системы, представленную сильно связанным ориентированным корневым графом, с ограниченной емкостью дуги (в том смысле, что только ограниченное количество сообщений может быть отправлено по дуге за определенный интервал времени). Граф может быть статическим или динамическим, т.е. меняющимся во времени. Для статического графа предлагается алгоритм построения прямого и обратного остовных деревьев с оценкой времени O(n / k + d), размером памяти в вершине и сообщения O(n d log q+), где n – число вершин графа, k – емкость дуги, d – длина максимального пути, q+ – максимальная полустепень исхода вершин. Построенные деревья используются в распределенном алгоритме вычисления функции от мультимножества значений, приписанных вершинам графа, за время не более 3d. В динамическом графе предполагается, что k = 1, дуга может появляться, исчезать или менять свой конец. Предлагается алгоритм мониторинга динамического графа, который доставляет в корень информацию о каждом изменении в графе за время O(n) или O(d) после прекращения изменений. Также предлагается алгоритм сбора информации о вершинах графа и разметки графа за время O(n). Эта разметка используется в алгоритме вычисления функции от мультимножества на динамическом графе за время O(n2) с размером сообщения O(log n) или за время O(n) с размером сообщения O(n log n). [ DOI ]

Публикация в формате сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл скрыть