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

Эта статья представляет собой обзор серии работ авторов, посвящённых исследованию распределенных систем. Рассматривается асинхронная модель распределённой системы, представленную сильно связанным ориентированным корневым графом, с ограниченной емкостью дуги (в том смысле, что только ограниченное количество сообщений может быть отправлено по дуге за определенный интервал времени). Граф может быть статическим или динамическим, т.е. меняющимся во времени. Для статического графа предлагается алгоритм построения прямого и обратного остовных деревьев с оценкой времени O ( n / k + d ), размером памяти в вершине и сообщения O ( n d log D⁺), где n - число вершин графа, k - емкость дуги, d - длина максимального пути, D⁺ - максимальная полустепень исхода вершин. Построенные кушниренко используются в распределенном алгоритме вычисления функции от мультимножества значений, приписанных вершинам графа, за время не более 3 d . В динамическом графе предполагается, что k = 1, дуга может появляться, исчезать или менять свой конец. Предлагается алгоритм мониторинга динамического графа, который доставляет в корень информацию о каждом изменении в графе за время O ( n ) или O ( d ) после прекращения изменений. Также предлагается алгоритм сбора информации о вершинах графа и разметки графа за время O ( n ). Эта разметка используется в алгоритме вычисления функции от мультимножества на динамическом графе за время O ( n²) с размером сообщения O ( log n ) или за время O ( n ) с размером сообщения O ( n log n ).

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

1. Valmir C. Barbosa. An introduction to distributed algorithms. // MIT Press, Cambridge, MA, USA, 1996

2. A.D. Kshemkalyani, M. Singhal. Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, March 2011. 756 pages

3. Michel Raynal. Distributed Algorithms for Message-Passing Systems. Springer Publishing Company, Incorporated, 2013. 500 pages

4. Fred B. Schneider. The State Machine Approach. A Tutorial. Fault-Tolerant Distributed Computing. LNCS 448, 1990, pp. 18-41

5. Бурдонов И.Б., Косачев А.С. Тестирование системы автоматов. Труды ИСП РАН, том 28, вып. 1, 2016 г., стр. 103-130. DOI: 10.15514/ISPRAS2016-28(1)-7

6. Бурдонов И.Б., Косачев А.С. Система автоматов: композиция по графу связей. Труды ИСП РАН, том 28, вып. 1, 2016 г., стр. 131-150. DOI: 10.15514/ISPRAS-2016-28(1)-8

7. Бурдонов И.Б., Косачев А.С. Система автоматов: условия детерминизма и тестирование. Труды ИСП РАН, том 28, вып. 1, 2016 г., стр. 151-184. DOI: 10.15514/ISPRAS-2016-28(1)-9

8. Бурдонов И.Б., Косачев А.С. Тестирование системы автоматов. Вестник Томского государственного университета. Управление, вычислительная техника и информатика, №1, 2017 г., стр. 67-75.

9. Бурдонов И.Б., Косачев А.С. Обобщенная модель системы автоматов. Вестник Томского государственного университета. Управление, вычислительная техника и информатика, №4(37), 2016 г., стр. 89-97.

10. Burdonov I.B., Kossatchev A.S. Buidling direct and back spanning trees by automata on a graph. Trudy ISP RAN/Proc. ISP RAS, vol. 26, issue 6, 2014 г., pp. 57-62. DOI: 10.15514/ISPRAS-2014-26(6)-4

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

12. Burdonov I.B., Kossatchev A.S., Kuliamin V.V. Parallel calculations by automata on direct and back spanning trees of a graph. Trudy ISP RAN/Proc. ISP RAS, vol. 26, issue 6, 2014 г., pp 63-66. DOI: 10.15514/ISPRAS-2014-26(6)-5

13. Бурдонов И.Б., Косачев А.С. Мониторинг динамически меняющегося графа. Труды ИСП РАН, том 27, вып. 1, 2015 г., стр. 69-96. DOI: 10.15514/ISPRAS2015-27(1)-5

14. Бурдонов И.Б., Косачев А.С. Параллельные вычисления на динамически меняющемся графе. Труды ИСП РАН, том 27, вып. 2, 2015 г., стр. 189-220. DOI: 10.15514/ISPRAS-2015-27(2)-12

15. Бурдонов И.Б., Косачев А.С. Исследование ориентированного графа коллективом неподвижных автоматов. Программная инженерия, том 8, № 1, 2017 г., стр. 16-25

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

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

18. Lynch, Nancy A.: Distributed algorithms. The Morgan Kaufmann Series in Data Management Systems. Kaufmann, San Francisco, Calif., 1996, pp. 904. ISBN 1-55860-348-4.

19. David Peleg. Distributed computing — A Locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications. 2000, 359 pp.

20. Camil Demetrescu, Irene Finocchi, and Giuseppe F. Italiano. Dynamic Graphs. In Handbook of Data Structures and Applications. Oct 2004, 36-1 -36-20. ISBN: 978-1-58488-435-4.

21. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков, Наука, Главная редакция физико-математической литературы, Москва, 1988.

22. Tary G. Le probl`eme des labyrinthes. Nouv Ann Math 14, 1895.