Preview

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

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

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

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

Аннотация

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

Об авторах

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

109004, Россия, г. Москва, ул. А. Солженицына, дом 25



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

109004, Россия, г. Москва, ул. А. Солженицына, дом 25



В. В. Кулямин
Институт системного программирования им. В.П. Иванникова РАН; Московский государственный университет имени М.В. Ломоносова; Национальный исследовательский университет «Высшая школа экономики»
Россия

109004, Россия, г. Москва, ул. А. Солженицына, дом 25

119991 ГСП-1 Москва, Ленинские горы, МГУ имени М.В. Ломоносова, 2-й учебный корпус, факультет ВМК

101000, Россия, г. Москва, ул. Мясницкая, д. 20



А. Н. Томилин
Институт системного программирования им. В.П. Иванникова РАН; Московский государственный университет имени М.В. Ломоносова
Россия

109004, Россия, г. Москва, ул. А. Солженицына, дом 25

119991 ГСП-1 Москва, Ленинские горы, МГУ имени М.В. Ломоносова, 2-й учебный корпус, факультет ВМК



В. З. Шнитман
Институт системного программирования им. В.П. Иванникова РАН; Московский физико-технический институт
Россия

109004, Россия, г. Москва, ул. А. Солженицына, дом 25

141700, Московская облаcть, г. Долгопрудный, Институтский пер., 9



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

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.


Рецензия

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


Бурдонов И.Б., Косачев А.С., Кулямин В.В., Томилин А.Н., Шнитман В.З. Асинхронные распределенные алгоритмы на статических и динамических ориентированных корневых графах. Труды Института системного программирования РАН. 2018;30(1):69-88. https://doi.org/10.15514/ISPRAS-2018-30(1)-5

For citation:


Burdonov I.B., Kossatchev A.S., Kuliamin V.V., Tomilin A.N., Shnitman V.Z. Asynchronous Distributed Algorithms for Static and Dynamic Directed Rooted Graphs. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(1):69-88. https://doi.org/10.15514/ISPRAS-2018-30(1)-5



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


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