Asynchronous Distributed Algorithms for Static and Dynamic Directed Rooted Graphs
https://doi.org/10.15514/ISPRAS-2018-30(1)-5
Abstract
The paper provides a review of distributed graph algorithms research conducted by authors. We consider an asynchronous distributed system model represented by a strongly connected directed rooted graph with bounded edge capacity (in a sense that only a bounded number of messages can be sent through an edge in a given time interval). A graph can be static or dynamic, i.e. changing. For a static graph we propose a spanning (in- and out-) tree construction algorithm of time complexity O ( n / k + d ), requiring O ( n d log D+) message size and the same size of memory of each computing agent located in graph vertex, where n is the number of vertices of the graph, k is the capacity of an edge, d is the maximum length of simple path in the graph, D+ is the maximum outdegree of the vertices. The spanning trees constructed can be used in distributed computation of a function of the multiset of values assigned to graph vertices in a time not greater than 3 d . In a dynamic graph we suppose that k = 1 and an edge can appear, disappear, or change its end. We propose a dynamic graph monitoring algorithm than delivers information on any change to the root of the graph in O (n) or O ( d ) after the changes are stopped. We also propose graph exploration and marking algorithm with time complexity O ( n ). The marking provided by it is used in distributed computation of a function of the multiset of values assigned to dynamic graph vertices, which can be performed in time O ( n2) with messages of size O ( log n ) or in time O ( n ) with messages of size O ( n log n ).
About the Authors
I. B. Burdonov
Ivannikov Institute for System Programming of the RAS
Russian Federation
Russian Federation
A. S. Kossatchev
Ivannikov Institute for System Programming of the RAS
Russian Federation
Russian Federation
V. V. Kuliamin
Ivannikov Institute for System Programming of the RAS; Lomonosov Moscow State University; National Research University Higher School of Economics (HSE)
Russian Federation
Russian Federation
A. N. Tomilin
Ivannikov Institute for System Programming of the RAS; Lomonosov Moscow State University
Russian Federation
Russian Federation
V. Z. Shnitman
Ivannikov Institute for System Programming of the RAS; Moscow Institute of Physics and Technology (State University)
Russian Federation
Russian Federation
References
1. Barbosa V.C. An introduction to distributed algorithms. MIT Press, Cambridge, MA, USA, 1996
2. Kshemkalyani A.D., Singhal M. Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, March 2011
3. Raynal M. Distributed Algorithms for Message-Passing Systems. Springer Publishing Company, Incorporated, 2013
4. Schneider F.B. The State Machine Approach. A Tutorial. Fault-Tolerant Distributed Computing. LNCS 448, 1990, pp. 18-41
5. Burdonov I.B., Kossatchev A.S. Testing of automata system. Trudy ISP RAN/Proc. ISP RAS, vol. 28, issue 1, 2016, pp. 103-130. DOI: 10.15514/ISPRAS2016-28(1)-7 (in Russian).
6. Burdonov I.B., Kossatchev A.S. Automata system: composition according to graph of links. Trudy ISP RAN/Proc. ISP RAS, vol. 28, issue 1, 2016, pp. 131-150. DOI: 10.15514/ISPRAS-2016-28(1)-8 (in Russian).
7. Burdonov I.B., Kossatchev A.S. Automata system: determinism conditions and testing. Trudy ISP RAN/Proc. ISP RAS, vol. 28, issue 1, 2016, pp. 151-184. DOI: 10.15514/ISPRAS-2016-28(1)-9 (in Russian).
8. Burdonov I.B., Kossatchev A.S. Testing of automata system. Vestnik Tomskogo gosudarstvennogo universiteta. [Bulletin of Tomsk State University. Management, Computer Science and Informatics], № 1, 2017, pp. 67-75 (in Russian).
9. Burdonov I.B., Kossatchev A.S. Generalized model of automata system. Vestnik Tomskogo gosudarstvennogo universiteta. [Bulletin of Tomsk State University. Management, Computer Science and Informatics], № 4(37), 2016, pp. 89-97 (in Russian).
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. Burdonov I.B., Kossatchev A.S., Kuliamin V.V. Parallel computations on a graph. Programming and Computer Software, vol. 41, № 1, 2015, pp. 1-13. DOI: 10.1134/S0361768815010028.
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. Burdonov I.B., Kossatchev A.S. Monitoring of dynamically changed graph. Trudy ISP RAN/Proc. ISP RAS, vol. 27, issue 1, 2015, pp. 69-96. DOI: 10.15514/ISPRAS2015-27(1)-5 (in Russian).
14. Burdonov I.B., Kossatchev A.S. Parallel Calculations on Dynamic Graph. Trudy ISP RAN/Proc. ISP RAS, vol. 27, issue 2, 2015, pp. 189-220. DOI: 10.15514/ISPRAS-2015-27(2)-12 (in Russian).
15. Burdonov I.B., Kossatchev A.S. Analysis of directed graph by a set of unmoving automata. Programmnaya inzheneriya [Software Engineering], vol. 8, № 1, pp. 16-25 (in Russian)
16. Bourdonov I.B. Traversal of an Unknown Directed Graph by a Finite Robot. Programming and Computer Software, vol. 30, № 4, 2004, pp. 188-203. DOI: 10.1023/B:PACS.0000036417.58183.64
17. Bourdonov I.B. Backtracking Problem in the Traversal of an Unknown Directed Graph by a Finite Robot. Programming and Computer Software, vol. 30, № 6, 2004, pp. 305-322. DOI: 10.1023/B:PACS.0000049509.66710.3a
18. Lynch, N.A. Distributed algorithms. The Morgan Kaufmann Series in Data Management Systems. Kaufmann, San Francisco, Calif., 1996
19. Peleg D. Distributed computing – A Locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications. 2000
20. Demetrescu C., Finocchi I., and Italiano G.F. Dynamic Graphs. In Handbook of Data Structures and Applications, sec. 36, 2004
21. Kushnirenko A.G., Lebedev G.V. Programming for mathematicians. Nauka, Glavnaya redaktsiya fiziko-matematicheskoi literatury [Science, the main edition of physical and mathematical literature], Moscow, 1988 (in Russian)
22. Tary G. Le probl`eme des labyrinthes. Nouv Ann Math 14, 1895.
Review
For citations:
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
Email this article 