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

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

1. Бурдонов И.Б., Евтушенко Н.В., Косачев А.С., Пономаренко В.Н. К организации системы запросов в распределенной сети с кластерами-кликами. Труды ИСП РАН, 2026, т. 38, вып. 3 (часть 1), стр. 7-32. DOI: 10.15514/ISPRAS-2026-38(3)-1. / Burdonov I.B., Yevtushenko N.V., Kossatchev A.S., Ponomarenko V.N. On the query system organization of a clustered distributed network. Trudy ISP RAN/Proc. ISP RAS, vol. 38, issue 3 (part 1), 2026, pp. 7-32 (in Russian). DOI: 10.15514/ISPRAS-2026-38(3)-1.

2. Евин И.А. Введение в теорию сложных сетей. Компьютерные исследования и моделирование, 2010, т. 2, вып. 2, стр. 121-141, Доступно по ссылке: https://crm-en.ics.org.ru/uploads/crmissues/crm2010-2-2/crm10201.pdf, обращение 01.04.2026.

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

4. Milgram S. The Small World Problem. Psychology Today, 1967. Available at: https://snap.stanford.edu/class/cs224w-readings/milgram67smallworld.pdf, accessed 01.04.2026.

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

6. Kristina Vušković. 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, обращение 01.04.2026.

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

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

9. Алексеев В.Е., Захарова Д.В. Теория графов. Учебное пособие. Нижний Новгород: Нижегородский госуниверситет, 2017, 119 с. Доступно по ссылке: http://www.unn.ru/books/met_files/Theory_graph.pdf, обращение 01.04.2026.

10. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы матроиды, алгоритмы. Ижевск: НИЦ "РХД", 2001, 288 стр. Доступно по ссылке: https://creewick.github.io/study/courses/graphs/book.pdf, обращение 01.04.2026.

11. Бурдонов И.Б., Евтушенко Н.В., Косачев А.С. Безопасная реализация виртуальной сети на плоскости данных SDN. Труды ИСП РАН, том 33, вып. 1, 2021 г., стр. 123-136. DOI: 10.15514/ISPRAS–2021–33(1)–9, Доступно по ссылке: https://ispranproceedings.elpub.ru/jour/article/view/1378?sphrase_id=7259394, обращение 01.04.2026.