Проблема отката в ориентированной распределенной системе

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