On the query system organization of a distributed network with clusters of diameter no more than 2

On the query system organization of a distributed network with clusters of diameter no more than 2

Burdonov I.B. (ISP RAS, Moscow, Russia)
Yevtushenko N.V. (ISP RAS, Moscow, Russia; NRU HSE, Moscow, Russia)
Kossatchev A.S. (ISP RAS, Moscow, Russia)
Ponomarenko V.N. (ISP RAS, Moscow, Russia)

Abstract

In this paper, an improved model of a service-oriented architecture as a clustered distributed network is considered. The improvements are related to a query system proposed in the previous paper of the authors. The polling purpose is location determination of the closest node that can provide a required service. Proposed techniques provide the node reachability and duplication absence; moreover, a shortest path is utilized for providing the communication. In a clustered network, clusters as subgraphs of the network are selected. The duplication absence is guaranteed if a bipartite graph of clusters and common nodes of several clusters is a tree. For finding the nearest node with necessary features, a bypass is sequentially performed: at the rth step the terminal nodes of the bypass are examined which starts at the initial node and passes via r-1 intermediate nodes. In the previous paper, every cluster had to be a clique that is a graph of diameter one and a number of such clusters can be large. In this paper, this requirement is relaxed: a cluster can be a subgraph of diameter at most two. This is essential, since almost all graphs have a diameter at most two and secondly the cluster number approximately decreases by half and in the same way, the number of polling steps is decreased. We also show that for clusters of diameter bigger than two, it is not always possible to implement the duplication absence.

Keywords

distributed clustered network; service-oriented architecture; node reachability; message duplication; shortest path; graphs of diameter 2.

Edition

Proceedings of the Institute for System Programming, vol. 38, issue 4, part 1, 2026, pp. 7-24

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(4)-1

For citation

Burdonov I.B., Yevtushenko N.V., Kossatchev A.S., Ponomarenko V.N. On the query system organization of a distributed network with clusters of diameter no more than 2. Proceedings of the Institute for System Programming, vol. 38, issue 4, part 1, 2026, pp. 7-24 DOI: 10.15514/ISPRAS-2026-38(4)-1.

Full text of the paper in pdf (in Russian) Back to the contents of the volume