К организации системы запросов в распределенной сети с кластерами-кликами

Труды Института системного программирования РАН. 2026. Т. 38. № 3-1. С. 7–32.

Бурдонов И. Б., Евтушенко Н. В., Косачев А. С., Пономаренко В. Н.

В статье предложена модель кластеризованной распределённой сети для обработки запросов. В такой сети узлы являются вычислительными единицами, и каждый узел может запросить ту или иную услугу, которая может быть оказана каким-то другим, но заранее неизвестным, узлом сети. Для этого осуществляется опрос сети аналогичный поиску в ширину для того, чтобы найти ближайший узел с необходимыми свойствами. При этом обеспечивается достижимость узлов, отсутствие дублирования сообщений, а обмен сообщениями с найденным узлом идёт по кратчайшему пути. Модель нацелена на предотвращение перегрузки сети и ориентирована на минимизацию как времени выполнения опроса, так и размера требуемой для этого памяти в узлах и размеров сообщений. Кластеризованность распределённой сети означает, что сеть состоит из множества кластеров, каждый из которых есть подмножество узлов сети и соединяющих их рёбер. Рёбра графа, которые не принадлежат никакому кластеру, не используются для передачи сообщений, а переход из кластера в кластер осуществляется через общие узлы кластеров. Для того чтобы не было дублирования сообщений, требуется, чтобы граф кластеров был деревом. В данной статье показано, что необходимым требованиям удовлетворяет связный блоковый граф, то есть связный граф, блоки (компоненты двусвязности) которого являются кликами. Эти блоки и выбираются в качестве кластеров.

Ключевые слова: распределенная кластеризованная сеть, опрос сети, достижимость узлов, дублирование сообщений, кратчайший путь, блоковый граф