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

Для распределенной системы, в основе которой лежит ориентированный граф без кратных ребер и петель, рассматривается проблема отката (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²) и 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.