THE GRAPH DIAMETER OF A DISTRIBUTED SYSTEM WITH A GIVEN DOMINANT SET
A. Rappoport, Ilya I. Kurochkin · 9th International Conference "Distributed Computing and Grid Technologies in Science and Education" · 2021
In this work consider a distributed computing system in which the control functions are dispersed inseveral dominant nodes that are directly connected to all the others. This configuration reduces thevulnerability of the entire network, since the failure of a single control element immediately disruptsits operation. On the other hand, the large length of the maximum shortest chain (diameter) increasesthe data transfer time, which is bad for the functioning of the entire system. The connection of themaximum shortest chain of a distributed network graph with the size of a certain dominant set isinvestigated. The structure of a graph with a maximum diameter on the set of all graphs with a givendominant set is presented, a diametrical chain is constructed, and the value of the extreme diameter isestimated. Based on this construction, it is possible to generate various network graphs with a givendominant set and a diameter that takes certain values. A number of operations are proposed thatchange the edge set of the original graph. As a result, this method provides a way to construct graphstructures with given metric characteristics.