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

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

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



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






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


Труды ИСП РАН, 2018, том 30, выпуск 2, страницы 167–194 (Mi tisp314)  

Проблема отката в ориентированной распределенной системе

И. Б. Бурдонов, А. С. Косачев

Институт системного программирования РАН

Аннотация: Для распределенной системы, в основе которой лежит ориентированный граф без кратных ребер и петель, рассматривается проблема отката (backtracing problem): как передать сообщение от конца дуги в ее начало. Ставится задача создания на графе структуры, позволяющей передавать сообщение из конца любой дуги в ее начало по кратчайшему пути. Такая структура в каждой вершине $a$ задаётся отображением номера вершины $b$ в номер исходящей дуги, через которую проходит кратчайших путь от $a$ к $b$. В частности, такое отображение позволяет симулировать в ориентированных распределенных системах алгоритмы решения задач на графе, разработанные для неориентированных распределенных систем. Это увеличивает время работы таких алгоритмов (в тактах, где время пересылки сообщения по дуге не превосходит 1 такт) не более чем в $k$ раз, где $k$ диаметр графа, $k<n$, и $n$ — число вершин графа. В разделе 2 описывается используемая асинхронная модель распределенной системы. Раздел 3 содержит основные определения и обозначения, а раздел 4 — постановку задачи. В разделе 5 описываются два вспомогательных алгоритма коррекции поддеревьев, применение которых позволяет строить остовные деревья кратчайших путей: прямого дерева, ориентированного от корня графа, и обратного дерева, ориентированного к корню графа. Раздел 6 содержит описание различных способов передачи сообщений по графу. В разделе 7 предлагаются два алгоритма построения в памяти автомата корня графа описаний прямого и обратного остовных деревьев кратчайших путей, а в разделе 8 — основанные на них алгоритмы построения требуемого отображения: «быстрый» алгоритм с оценками $T = O ( n )$ и $N = O ( n )$ и «экономный» алгоритм с оценками $T = O ( n^2)$ и $N = O (1)$, где $T$ — время (в тактах) работы алгоритма, $N$ — число сообщений, одновременно передаваемых по дуге. В разделе 9 доказано, что эти оценки времени не улучшаемые. В разделе 10 «быстрый» алгоритм модифицируется для синхронной модели с $N =1$. Заключение подводит итоги и намечает направления дальнейших исследований.

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-07-00682
Работа частично поддержана проектом РФФИ № 17-07-00682 А.


DOI: https://doi.org/10.15514/ISPRAS-2018-30(2)-9

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

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

Тип публикации: Статья

Образец цитирования: И. Б. Бурдонов, А. С. Косачев, “Проблема отката в ориентированной распределенной системе”, Труды ИСП РАН, 30:2 (2018), 167–194

Цитирование в формате AMSBIB
\RBibitem{BurKos18}
\by И.~Б.~Бурдонов, А.~С.~Косачев
\paper Проблема отката в ориентированной распределенной системе
\jour Труды ИСП РАН
\yr 2018
\vol 30
\issue 2
\pages 167--194
\mathnet{http://mi.mathnet.ru/tisp314}
\crossref{https://doi.org/10.15514/ISPRAS-2018-30(2)-9}
\elib{http://elibrary.ru/item.asp?id=34996258}


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

    ОТПРАВИТЬ: 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
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:107
    Полный текст:37
    Литература:12
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020