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

Рассматриваются распределённые алгоритмы решения задач на неориентированных графах. В разделе 2 определяется используемая модель, особенностью которой является наличие корня, с которого начинается и в котором заканчивается работа алгоритма. Описываются синхронная и асинхронная разновидности модели. В разделе 3 предлагаются алгоритмы решения любых задач, основанные на сборе информации о всём графе в корне или в каждой вершине, а также, если необходимо, разметке графа (его вершин и/или рёбер). Акцент сделан на времени работы алгоритма, а при минимальном времени - на экономии памяти в вершинах и суммарном объёме пересылаемых сообщений. В остальной части статьи рассматриваются оптимизации для конкретных задач: построение максимального независимого множества (MIS - Maximal Independent Set), поиск множества всех мостов в графе (FSB - Finding Set of Bridges), построение минимального остовного дерева во взвешенном графе (MST - Minimum Spanning Tree). В разделе 4 предлагается модификация общих алгоритмов для этих задач, уменьшающая оценки размера памяти вершин и сообщений. Раздел 5 содержит нижние оценки сложности решения этих задач. В разделе 6 для синхронной модели уменьшается время работы алгоритмов с разметкой графа до нижней границы для задач с однозначным решением, зависящим только от простых циклов графа, в частности, FSB, MST и задачи поиска гальмильтонова цикла. В разделе 7 рассматриваются оптимальные по времени алгоритмы для FSB и MST для обеих моделей: синхронной и асинхронной. Заключение подводит итоги и намечает направления дальнейших исследований.

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

1. Joseph JaJa. An Introduction to Parallel Algorithms, Addison-Wesley, 1992, ISBN 0-201-54856-9.

2. Stephen A.Cook. An overview of computational complexity. Communications of the ACM. 1983, June, Vol.26, No.6.

3. Luis Barba. LITERATURE REVIEW: Parallel algorithms for the maximal independent set problem in graphs. October 2012. web-site:

4. http://cglab.ca/~lfbarba/parallel_algorithms/Literature_Review.pdf.

5. (accessed: December 2016)

6. R.M. Karp, A. Wigderson. A fast parallel algorithm for the maximal independent set problem. Proc. 16th Annual ACM Symposium on Theory of Computing. ACM, New York, 1984, pp. 266–272.

7. M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing. 1986, Vol.15, No 4., pp. 1036-1053. DOI:10.1137/0215074.

8. Noga Alon, Laszlo Babai, Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms. 1986, December, Vol. 7, Issue 4, pp. 567-583.

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

10. N.A. Lynch. Distributed Algorithms. The Morgan Kaufmann Series in Data Management Systems.1996, 904 pp.

11. Thomas Moscibroda. Locality, Scheduling, and Selfishness: Algorithmic Foundations of Highly Decentralized Networks. PhD thesis, ETH Zurich, 2006.

12. Y. Métivier, J. M. Robson, N. Saheb-Djahromi, A. Zemmar. An optimal bit complexity randomized distributed MIS algorithm. Distributed Computing. April 2011, Vol. 23, Issue 5, pp. 331–340.

13. Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2016, pp.270-277.

14. Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. Cornell University Library: https://arxiv.org/pdf/1506.05093v2.pdf (accessed: December 2016)

15. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. In Foundations of Computer Science (FOCS) 2012, IEEE, 2012, pp. 321–330. Also coRR abs/1202.1983v3.

16. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. What cannot be computed locally! In the Proc. of the Int’l Symp. on Princ. of Dist. Comp. (PODC). ACM, 2004, pp 300–309.

17. И. Бурдонов, А. Косачев. Общий подход к решению задач на графах коллективом автоматов. Труды ИСП РАН, том 29, вып. 2, 2017, стр. 27-76.

18. И. Бурдонов, А. Косачев. Размер памяти для хранения упорядоченного корневого графа. Труды ИСП РАН, том 29, вып. 2, 2017, стр. 7-26.