К организации системы запросов в распределенной сети с кластерами диаметра не более 2
К организации системы запросов в распределенной сети с кластерами диаметра не более 2
Аннотация
В статье усовершенствуется предложенная в предыдущей статье авторов модель кластеризованной распределённой сети с опросом, соответствующая сервис-ориентированной архитектуре. Целью опроса является нахождение ближайшего узла, готового оказать требуемую услугу (сервис) как можно раньше. Предлагаемые алгоритмы обеспечивают достижимость узлов, отсутствие дублирования сообщений, и обмен сообщениями с найденным узлом по кратчайшему пути. Кластеризованность сети означает, что в графе сети выделены подграфы – кластеры, покрывающие все узлы графа. Отсутствие дублирования гарантируется, если двудольный граф кластеров и общих (принадлежащих нескольким кластерам) узлов является деревом. Для поиска ближайшего узла с нужными свойствами опрос выполняется последовательно по раундам: на r-м раунде опрашиваются узлы на концах путей, начинающихся в начальном узле, запрашивающем услугу, и проходящих через r 1 промежуточных общих узлов. В предыдущей статье авторов рассматривалась кластеризация сети, при которой каждый кластер был кликой, т.е. графом диаметра 1, однако число таких кластеров может получиться достаточно большим. В настоящей статье это требование ослабляется: кластер может быть графом диаметра не более 2. Это существенное ослабление, поскольку, во-первых, как известно, почти все графы имеют диаметр 2, во-вторых, число кластеров уменьшается примерно в 2 раза и также примерно в 2 раза уменьшается число требуемых раундов. Кроме того, показывается, что для кластеров диаметра больше 2 избежать дублирования не всегда возможно.
Ключевые слова
Издание
Труды Института системного программирования РАН, том 38, вып. 4, часть 1, 2026, стр. 7-24.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).
DOI: 10.15514/ISPRAS-2026-38(4)-1
Для цитирования
Полный текст статьи в формате pdf
Вернуться к содержанию тома