A general approach to solving problems on graphs by collective automata

We propose a general method to solve graph problems by a set of automata (computational agents) located in vertices of undirected ordered connected rooted graph and communicating by passing messages along graph edges. The automata are semi-robots, i.e., their internal memory size is sufficient to store values depending on the number of vertices and edges of the graph (n and m, correspondingly) but is too small to store the complete graph description. Section 2 presents classification of graph-based distributed computational models depending on internal memory size of vertex automaton, vertex automaton operation time, and edge capacity (the number of messages that are passing along an edge simultaneously). We choose for further use the model of maximum parallelism, having zero automaton operation time and unbounded edge capacity. It allows to obtain lower complexity bounds on distributed graph problems. Section 3 describes algorithm complexity assessment rules. Section 4 presents basic message processing procedures and message classification according to paths passed by them and methods of message processing by vertex automaton. We propose to construct algorithms solving graph problems on the base of the procedures considered, and present some examples in further sections. Sections 5-9 describe distributed algorithms for spanning tree construction, for task termination detection (based on detection of absence of messages used by the task), for shortest paths tree construction, for graph vertices enumeration, for collecting graph structure information in the root automaton memory (if it is unbounded). The algorithms proposed has linear time complexity in n and m, and use linear in n and m number of messages. Section 10 considers construction of maximum weight path in a weighted graph, which is the NP problem. We propose the algorithm that for the sake of using unbounded number of messages can solve this problem in linear time in n and m. The conclusion summarizes the paper and draws directions of further research: constructing algorithms for other graph problems and generalization of the approach to directed, non-deterministic and dynamic graphs.

undirected graphs, graph problems, asynchronous distributed systems, distributed algorithms

1. I. Burdonov, A. Kosachev. Graph learning by a set of automata. Trudy ISP RAN/Proc. ISP RAS, vol. 26, issue 2, 2014, pp. 43-86 (in Russian). DOI: 10.15514/ISPRAS-2014-26(2)-2

2. I. Burdonov, A. Kosachev. Analysis of a Graph by a Set of Interacting Automata. «Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naja tehnika i informatika» [Tomsk State University. Journal of Control and Computer Science], №3, 2014, pp. 67-75. (in Russian).

3. I. Burdonov, A. Kosachev. Graph learning by a set of automata. The nondeterministic case. Trudy ISP RAN/Proc. ISP RAS, vol. 27, issue 1, 2015, pp. 51-68, (in Russian). DOI: 10.15514/ISPRAS-2015-27(1)-4

4. I.B. Bourdonov, A.S. Kossatchev, V.V. Kulyamin. Analysis of a Graph by a Set of Automata. Programming and Computer Software, Vol. 41, No. 6, 2015, pp. 307-310. DOI: 10.1134/S0361768815060031

5. I.B. Burdonov, A.S. Kosachev. Analysis of a Graph by a Set of Moving Automata. "Programmnaja inzhenerija" [Software Engineering], 2016, Vol. 7, № 12, pp. 559-567, (in Russian).

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

7. I.B.Burdonov, A.S.Kosachev, V.V.Kuljamin. 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 (in Russian). DOI: 10.15514/ISPRAS-2014-26(6)-5

8. I.B. Bourdonov, A.S. Kossatchev, V.V. Kulyamin. Parallel Computations on a Graph. Programming and Computer Software, Vol. 41, No. 1, 2015, pp. 1-13. DOI: 10.1134/S0361768815010028

9. I. Burdonov, A. Kosachev. Monitoring of dynamically changed graph. Trudy ISP RAN/Proc. ISP RAS, vol. 27, issue 1, 2015, pp. 69-96 (in Russian). DOI: 10.15514/ISPRAS-2015-27(1)-5

10. I. Burdonov, A. Kosachev. Parallel Calculations on Dynamic Graph. Trudy ISP RAN/Proc. ISP RAS, vol. 27, issue 2, 2015, pp. 189-220 (in Russian). DOI: 10.15514/ISPRAS-2015-27(2)-12

11. I.B. Burdonov, A.S. Kosachev. Analysis of an Oriented Graph by a Set of Motionless Automata. "Programmnaja inzhenerija" [Software Engineering], 2017, Vol. 8, № 1, pp. 16-25, (in Russian).

12. I. B. Bourdonov, A.S. Kossatchev, V V. Kuliamin. Irredundant Algorithms for Traversing Directed Graphs: The Nondeterministic Case. Programming and Computer Software, Vol. 30, No. 1, 2004, pp. 2-17. DOI: 10.1023/A:1025733107700

13. 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. xx-xx (in Russian). DOI: 10.15514/ISPRAS-2017-29(2)-1

14. I.B. Burdonov, A.S. KosachevAnalysis of a Graph by an Automaton. "Programmnaja inzhenerija" [Software Engineering], 2016, №11, pp. 498-508, (in Russian).

15. I.B. Bourdonov. Traversal of an Unknown Directed Graph by a Finite Robot. Programming and Computer Software, Vol. 30, No. 4, 2004, pp. 188-203. DOI: 10.1023/B:PACS.0000036417.58183.64

16. I. B. Bourdonov. Backtracking Problem in the Traversal of an Unknown Directed Graph by a Finite Robot. Programming and Computer Software, Vol. 30, No. 4, 2004, pp. 305-322. DOI: 10.1023/B:PACS.0000049509.66710.3a

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

18. Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.