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

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

Бурдонов И.Б. (ИСП РАН, Москва, Россия)
Евтушенко Н.В. (ИСП РАН, Москва, Россия; НИУ ВШЭ, Москва, Россия)
Косачев А.С. (ИСП РАН, Москва, Россия)
Пономаренко В.Н. (ИСП РАН, Москва, Россия)

Аннотация

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

Ключевые слова

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

Издание

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

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

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

Для цитирования

Бурдонов И.Б., Евтушенко Н.В., Косачев А.С., Пономаренко В.Н. К организации системы запросов в распределённой сети с кластерами-кликами. Труды Института системного программирования РАН, том 38, вып. 3, часть 1, 2026, стр. 7-32. DOI: 10.15514/ISPRAS-2026-38(3)-1.

Полный текст статьи в формате pdf Вернуться к содержанию тома