Distributed algorithms on rooted undirected graphs

Distributed algorithms of solving problems on undirected graphs are considered. In section 2, a model is defined featuring a root as a starting and ending point of the algorithm execution. Synchronous and asynchronous versions of the model are described. In section 3, algorithms of solving any problems are suggested based on collecting information on the whole graph in the root or in any vertex, as well as, on the graph labeling (its vertices and/or edges), if required. Emphasis is made on the time of the algorithm execution or on saving memory in vertices and total size of transferred messages, if this time is minimal. The rest of the paper considers optimizations for particular problems: creation of Maximal Independent Set (MIS), Finding Set of Bridges (FSB), creation of Minimum Spanning Tree (MST) in a edge-weighted graph. In section 4, a modification of general algorithms for these problems is suggested decreasing the estimate of memory size of vertices and messages. Section 5 includes lower-bound estimates of solution complexity for these problems. In section 6, for synchronous model, the time of algorithms execution with graph labeling is decreased to the lower bound for problems with single-valued solution depending on only simple cycles of the graph, in particular, FSB, MST and the problem of Hamiltonian cycle search. In section 7, time-optimal algorithms for FSB and MST are considered for both synchronous and asynchronous models. Conclusion summarizes the results and outlines the directions for further research.

rooted undirected graph, distributed algorithms, graph problems, maximal independent set, minimum spanning tree, finding bridges

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: http://cglab.ca/~lfbarba/parallel_algorithms/Literature_Review.pdf. (accessed: December 2016)

4. 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.

5. 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.

6. 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.

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

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

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

10. 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.

11. 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.

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

13. 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.

14. 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.

15. I. Burdonov, A. Kossatchev. A general approach to solving problems on graphs by collective automata. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 2, 2017, pp. 27-76 (in Russian).

16. I. Burdonov, A. Kosachev. Size of the memory for storage of ordered rooted graph. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 2, 2017, pp. 7-26 (in Russian).