RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды ИСП РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды ИСП РАН, 2018, том 30, выпуск 1, страницы 69–88 (Mi tisp296)  

Asynchronous distributed algorithms for static and dynamic directed rooted graphs

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

I. B. Burdonova, A. S. Kossatcheva, V. V. Kuliaminbac, A. N. Tomilinba, V. Z. Shnitmanda

a Ivannikov Institute for System Programming of the RAS
b Lomonosov Moscow State University
c National Research University Higher School of Economics (HSE)
d Moscow Institute of Physics and Technology (State University)

Аннотация: Эта статья представляет собой обзор серии работ авторов, посвящённых исследованию распределенных систем. Рассматривается асинхронная модель распределённой системы, представленную сильно связанным ориентированным корневым графом, с ограниченной емкостью дуги (в том смысле, что только ограниченное количество сообщений может быть отправлено по дуге за определенный интервал времени). Граф может быть статическим или динамическим, т.е. меняющимся во времени. Для статического графа предлагается алгоритм построения прямого и обратного остовных деревьев с оценкой времени $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)$.

Ключевые слова: распределенные алгоритмы, асинхронные системы, ориентированный граф, корневой граф, динамический граф, параллельные вычисления.

DOI: https://doi.org/10.15514/ISPRAS-2018-30(1)-5

Полный текст: PDF файл (881 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
Язык публикации: английский

Образец цитирования: I. B. Burdonov, A. S. Kossatchev, V. V. Kuliamin, A. N. Tomilin, V. Z. Shnitman, “Asynchronous distributed algorithms for static and dynamic directed rooted graphs”, Труды ИСП РАН, 30:1 (2018), 69–88

Цитирование в формате AMSBIB
\RBibitem{BurKosKul18}
\by I.~B.~Burdonov, A.~S.~Kossatchev, V.~V.~Kuliamin, A.~N.~Tomilin, V.~Z.~Shnitman
\paper Asynchronous distributed algorithms for static and dynamic directed rooted graphs
\jour Труды ИСП РАН
\yr 2018
\vol 30
\issue 1
\pages 69--88
\mathnet{http://mi.mathnet.ru/tisp296}
\crossref{https://doi.org/10.15514/ISPRAS-2018-30(1)-5}
\elib{http://elibrary.ru/item.asp?id=32663694}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tisp296
  • http://mi.mathnet.ru/rus/tisp/v30/i1/p69

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:95
    Полный текст:30
    Литература:8
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020