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

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

1. Бурдонов И.Б., Евтушенко Н.В., Косачев А.С., Пономаренко В.Н. Модель распределённой сети, в которой хосты могут выполнять функцию коммутации сообщений. Труды ИСП РАН, том 37, вып. 4, часть 1, 2025 г., стр. 7-30. DOI: 10.15514/ISPRAS–2025–37(4-1)–1.

2. Бурдонов И.Б., Евтушенко Н.В., Косачев А.С., Пономаренко В.Н. Кластеризация услуг распределённой сети, в которой хосты могут выполнять функцию коммутации сообщений. Труды ИСП РАН, том 37, вып. 5, 2025 г., стр. 7-32. DOI: 10.15514/ISPRAS–2025–37(5)–1.

3. Евин И.А. Введение в теорию сложных сетей. Компьютерные исследования и моделирование, 2010, т. 2, вып. 2, стр. 121-141.

4. Мир тесен (граф). Доступно по ссылке: https://ru.wikipedia.org/wiki/Мир_тесен_(граф), обращение: 15.04.2026.

5. Milgram S. The Small World Problem. Psychology Today, 1967.

6. Мир тесен. Доступно по ссылке: https://ru.wikipedia.org/wiki/Мир_тесен, обращение: 15.04.2026.

7. Карпов Д.В. Теория графов. МЦНМО, 2022. ISBN 978-5-4439-1690-3. Доступно по ссылке: https://www.klex.ru/2ad3, обращение: 15.04.2026.

8. Vušković K. Even-hole-free graphs: A survey // Applicable Analysis and Discrete Mathematics, 2010, vol. 4, no. 2, pp. 219-240. doi:10.2298/AADM100812027V. Доступно по ссылке: https://doiserbia.nb.rs/img/doi/1452-8630/2010/1452-86301000027V.pdf, обращение: 15.04.2026.

9. Блоковый граф. Доступно по ссылке: https://ru.wikipedia.org/wiki/Блоковый_граф, обращение: 15.04.2026.

10. Hamelink R.C. A partial characterization of clique graphs. Journal of Combinatorial Theory, 1968, vol. 5, pp. 192-197, https://www.sciencedirect.com/science/article/pii/S0021980068800559?via%3Dihub, accessed: 15.04.2026. DOI: 10.1016/S0021-9800(68)80055-9.

11. Кликовый граф. Доступно по ссылке: https://ru.wikipedia.org/wiki/Кликовый_граф#cite_note-_4fa7c03ed9057c22-1, обращение: 15.04.2026.

12. Howorka E. On metric properties of certain clique graphs. Journal of Combinatorial Theory, Series B, 1979, vol. 27, no. 1, pp. 67-74. Available at: https://www.sciencedirect.com/science/article/pii/0095895679900698?via%3Dihub, accessed: 15.04.2026. DOI: 10.1016/0095-8956(79)90069-8.