Asynchronous distributed algorithms for static and dynamic directed rooted graphs
I. B. Burdonova,
A. S. Kossatcheva,
V. V. Kuliaminbac,
A. N. Tomilinba,
V. Z. Shnitmanda a Ivannikov Institute for System Programming of the RAS
b Lomonosov Moscow State University
c National Research University Higher School of Economics (HSE)
d Moscow Institute of Physics and Technology (State University)
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(nd\log\Delta^+)$ 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,
$\Delta^+$ 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
$3d$. 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(n^2)$ with messages of size
$O(\log n)$ or in time
$O(n)$ with messages of size
$O(n\log n)$.
Keywords:
distributed algorithms, asynchronous systems, directed graph, rooted graph, dynamic graph, parallel computations.
Language: English
DOI:
10.15514/ISPRAS-2018-30(1)-5