Preview

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

Расширенный поиск

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

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

Полный текст:

Аннотация

Для распределенной системы, в основе которой лежит ориентированный граф без кратных ребер и петель, рассматривается проблема отката (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 ( n2) и N = O (1), где T - время (в тактах) работы алгоритма, N - число сообщений, одновременно передаваемых по дуге. В разделе 9 доказано, что эти оценки времени не улучшаемые. В разделе 10 «быстрый» алгоритм модифицируется для синхронной модели с N =1. Заключение подводит итоги и намечает направления дальнейших исследований.

Об авторах

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


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


Список литературы

1. Y. Afek and E. Gafni, Distributed Algorithms for Unidirectional Networks, SIAM J. Comput., vol. 23, No. 6, 1994, pp. 1152-1178.

2. И.Б.Бурдонов. Обход неизвестного ориентированного графа конечным роботом. Программирование, 2004, №4, стр.11-34.

3. И.Б.Бурдонов. Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом. Программирование, 2004, №6, стр.6-29.

4. И. Бурдонов, А. Косачев. Общий подход к решению задач на графах коллективом автоматов. Труды Института системного программирования РАН, том 29, вып. 2, 2017 г., стр. 27-76. DOI: 10.15514/ISPRAS-2017-29(2)-2.

5. И. Бурдонов, А. Косачев. Распределённые алгоритмы на корневых неориентированных графах. Труды Института системного программирования РАН, том 29, вып. 5, 2017 г., стр. 283-310. DOI: 10.15514/ISPRAS-2017-29(5)-14.

6. И. Бурдонов, А. Косачев. Размер памяти для хранения упорядоченного корневого графа. Труды Института системного программирования РАН, том 29, вып. 2, 2017 г., стр. 7-26. DOI: 10.15514/ISPRAS-2017-29(2)-1.

7. И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин. Параллельные вычисления на графе. Программирование, 2015, №1, стр. 3-20.


Для цитирования:


Бурдонов И.Б., Косачев А.С. Проблема отката в ориентированной распределенной системе. Труды Института системного программирования РАН. 2018;30(2):167-194. https://doi.org/10.15514/ISPRAS-2018-30(2)-9

For citation:


Burdonov I.B., Kossatchev A.S. Directed distributed system: Backtracking problem. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(2):167-194. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(2)-9

Просмотров: 100


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)