In this work consider a distributed computing system in which the control functions are dispersed in several dominant nodes that are directly connected to all the others. This configuration reduces the vulnerability of the entire network, since the failure of a single control element immediately disrupts its operation. On the other hand, the large length of the maximum shortest chain (diameter) increases the data transfer time, which is bad for the functioning of the entire system. The connection of the maximum shortest chain of a distributed network graph with the size of a certain dominant set is investigated. The structure of a graph with a maximum diameter on the set of all graphs with a given dominant set is presented, a diametrical chain is constructed, and the value of the extreme diameter is estimated. Based on this construction, it is possible to generate various network graphs with a given dominant set and a diameter that takes certain values. A number of operations are proposed that change the edge set of the original graph. As a result, this method provides a way to construct graph structures with given metric characteristics.
Distributed computing systems can be used to solve complex computational problems along
with clusters and MPP systems [1]. It is necessary to take into account the features of distributed
computing systems: the possibility of errors, the sudden shutdown of any computing node, the
heterogeneity of computing nodes and significant restrictions on the data exchange [2]. There is
"Bagof-Tasks" type of tasks for which calculations can be divided into many autonomous subtasks, and
data exchange is not required [
In paper [
Let's formulate the necessary concepts [
V n, E m .
By definition, diameter G diamG maxx, y, where x, y – distance, i.e. the length of the shortest chain over all pairs of vertices x, y V . A dominant set D is such a subset of vertices from V , that for any vertex y V \ D there is an edge x, y E, x D . The minimum size of such a subset is called the dominance number G .
A method is given for constructing a graph with a maximum diameter on a set of graphs with a
given dominant set of vertices [
Let D {xi ,i 1, s} is some dominating set of the required graph G . It has vertices from D V are not adjacent xi., x j E, i , j 1, s . Define in V \ D disjoint "dominated" subsets of vertices Vi Nxi – the neighborhood of vertex xi and their corresponding subgraphs Gi Gi Vi , Ei , by construction Vi V j , Ei E j , i, j 1, s .
We require the fulfillment of additional conditions on the structure of these subgraphs. And let's designate them (A) together with the already formulated conditions.
In these subgraphs, the vertices are divided into 2 disjoint subsets: Vi Vi1 Vi2 , and vertices from different subsets are not adjacent. In subgraphs Gi1 Gi1Vi1, Ei1 , Gi2 Gi2 Vi2 , Ei2 only interior edges are allowed, and at least one vertex from Vi2 is adjacent to a vertex from Vi11 . The main result can be formulated as Theorem 1.
If graph G GV , E with dominant set D {xi , i 1, s} satisfies the conditions (A), then the length of the maximal shortest path (diametrical) in it is equal to 3s 1 . This chain is: { y11 , x1 , y12 , y12 , x2 , y22 , …, y1s1 , xs1 , ys2 , xs , y1s } , where yi1 Vi1 , yi2 Vi2 .
In addition, on the set of all graphs with such a dominant set D the diameter 3s 1 . A
similar result on the estimation of the diameter was previously known [
As one of the possible ways to obtain a configuration with a given value of the diameter, one can use the introduction on the set of vertices of the dominant set D of the edges of the complete subgraph K p with p vertices 2 p s . This will make it possible to reduce the length of the diametrical chain in the new graph G p .
X s P-1
K p
S-2P+1 chain between the vertices x1 and x s , incident to the vertices x p and x2 p1 , including the edge between them from the complete subgraph K p . Then this chain, following Theorem 1, is obtained by removing 3 p 1 an edge from a chain of length 3s 1 and adding 3 edges shown by the dotted line. Therefore, its length is (G ) 3s 1 (3 p 1) 3 3(s p 1) . This implies Theorem 2: p
edge in G p .
In graph G p = G ( K p ) with dominant set D , ǀ D ǀ=s on р vertices of which a complete subgraph K p is constructed with diameter (G p ) 3(s p 1) , and the diametrical chain between x1 and x s consists of 3 fragments, and the middle fragment contains an edge ( x p , x2 p1 ) from K p .
For illustration, consider the case when p 2 and s 4 ,that is ( x p , x2 p1 ) = ( x2 , x3 ) – 1 Y 1
In an extreme graph, when there are no edges between vertices from D ( x1 , x4 ) = 11, and in the constructed graph G ( K 2 ) the length of the maximal chain (diametrical) ( x1 , x4 ) =9.
A method was proposed for constructing a graph with a maximum diameter on a set of graphs with a given size of the dominant set. The use of this method of constructing a graph of a telecommunication network allows avoiding both excessive centralization. It becomes possible to assess the time of data transmission in the network, with nodes operating on the basis of disjunctive logic. The structure of extreme graphs and estimates of parameters are presented: the number of edges and vertices, the type of the diametrical chain and the value of the maximum diameter. The results obtained were applied to graphs with two dominant vertices. The proposed approach can be used to construct graphs of telecommunication networks of structured distributed systems with a known dominant set and a certain value of the diameter.
The reported study was funded by RFBR according to the research project No. 19-07-00834. [1] Foster I., Kesselman C. (ed.). The Grid 2: Blueprint for a new computing infrastructure. –
Elsevier, 2003. [2] Li S. et al. A fundamental tradeoff between computation and communication in distributed computing //IEEE Transactions on Information Theory, Vol. 64, No.1, 2017. – pp. 109-128. [8] West D. B. et al. Introduction to graph theory. – Upper Saddle River, NJ : Prentice hall, Vol.2, 1996.