Directed distributed system: Backtracking problem

For a distributed system based on a directed graph without multiple edges and loops, the backtracing problem is considered: how to transfer a message from the final vertex of the arc to its initial vertex. The task is to create a structure on the graph that allows the message to be transmitted from the final vertex of the arc to its initial vertex in the minimum time, i.e. on the shortest path. Such a structure at each vertex a is given by mapping the number of vertex b to the number of the outgoing arc through which the shortest path passes from a to b . In particular, such a mapping makes it possible to simulate, in directed distributed systems, algorithms for solving problems on a graph, developed for unditected distributed systems. This increases the running time of such algorithms by not more than k times, where k does not exceed the diameter of the graph, k < n , where n is the number of vertices of the graph. Section 2 describes the asynchronous model of the distributed system used. Section 3 contains the basic definitions and notation, and Section 4 - the statement of the problem. Section 5 describes two auxiliary algorithms for subtree correction, the application of which makes it possible to construct spanning trees of shortest paths: a out-tree and an in-tree. Section 6 contains a description of the various methods for transmitting messages over the graph. In Section 7, two algorithms are proposed for constructing in the memory of the graph root automaton the descriptions of spanning out- and in- shortest path trees, and in Section 8, the algorithms for constructing the required mapping based on them: a "fast" algorithm with T = O ( n ) and N = O ( n ) and an "economical" algorithm with T = O ( n²) and N = O (1), where T is the running time of the algorithm, N is the number of messages simultaneously transmitted along the arc. In Section 9 it is proved that these estimates of time are not improved. In Section 10, the "fast" algorithm is modified for a synchronous model with N = 1. The conclusion sums up and outlines directions for further research.

directed graph, rooted graph, numbered graph, distributed algorithms, graph problems, backtracing problem, shortest paths

1. Y. Afek and E. Gafni, Distributed Algorithms for Unidirectional Networks, SIAM J. Comput., Vol. 23, No. 6, 1994, pp. 1152-1178.

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

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

4. I.Burdonov, A.Kossatchev. 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). DOI: 10.15514/ISPRAS-2017-29(2)-2.

5. I.Burdonov, A.Kossatchev. Distributed algorithms on root undirected graphs. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 5, 2017, pp. 283-310 (in Russian). DOI: 10.15514/ISPRAS-2017-29(5)-14.

6. I.Burdonov, A.Kossatchev. The size of the memory for storing the ordered root graph. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 2, 2017, pp. 7-26 (in Russian). DOI: 10.15514/ISPRAS-2017-29(2)-1.

7. I.B. Burdonov, 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.