Asynchronous distributed algorithms for static and dynamic directed rooted graphs

Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 1. P. 69–88.

Burdonov I. B., Kossatcheva A. S., Кулямин В. В., Tomilin A. N., Shnitman V. Z.

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)O(n/k+d), requiring O(ndlogΔ+)O(ndlog⁡Δ+)message size and the same size of memory of each computing agent located in graph vertex, where nn is the number of vertices of the graph, kk is the capacity of an edge, dd is the maximum length of simple path in the graph, Δ+Δ+ 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 3d3d. In a dynamic graph we suppose that k=1k=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)O(n) or O(d)O(d) after the changes are stopped. We also propose graph exploration and marking algorithm with time complexity O(n)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)O(n2)with messages of size O(logn)O(log⁡n) or in time O(n)O(n) with messages of size O(nlogn)O(nlog⁡n).

Ключевые слова: directed graphs, asynchronous systems, distributed algorithms, rooted graph, dynamic graph, parallel computations