СПОСОБ И СИСТЕМА ЦИКЛИЧЕСКОГО РАСПРЕДЕЛЕННОГО АСИНХРОННОГО ОБМЕНА СООБЩЕНИЯМИ СО СЛАБОЙ СИНХРОНИЗАЦИЕЙ ДЛЯ РАБОТЫ С БОЛЬШИМИ ГРАФАМИ Российский патент 2021 года по МПК G06F9/52 G06F15/173 

ОБЛАСТЬ ТЕХНИКИ

[0001] Настоящее техническое решение относится к области информационных технологий, а также к области управления большими графовыми данными, в частности, к способам передачи графовой информации между узлами сети с помощью циклического распределенного асинхронного обмена сообщениями со слабой синхронизацией.

УРОВЕНЬ ТЕХНИКИ

[0002] Из уровня техники известен подход передачи сообщений с помощью построения графовой модели узлов обмена, например, различные реализации модели Bulk Synchronous Parallel (BSP) (https://en.wikipedia.org/wiki/Bulk_synchronous_parallel), в частности, модель, реализованная в Apache Giraph (http://giraph.apache.org/intro.html). Данная модель основана на алгоритме поиска кратчайшего пути между узлами обмена, для чего выполняется определение расстояния между вершинами в графовой структуре.

[0003] Известными решениями для поиска кратчайшего пути является - поиск кратчайшего пути между двумя вершинами взвешенного графа (Взвешенным называется граф, ребра которого имеют веса). Наиболее эффективным алгоритмом поиска кратчайшего пути на графах с не отрицательными весами является алгоритм Dijkstra (https://en.wikipedia.org/wiki/Diikstra%27s_algorithm). Алгоритм требует последовательного поиска пути от наиболее ближайшей (на текущий момент) вершины в первую очередь. Т.е. если известно, что путь может проходить через обе вершины, то алгоритм продолжает поиск с ближайшей из двух вершин.

[0004] Алгоритм CMMS (критерий - OUT) позволяет выполнять поиск кратчайшего пути в параллельном режиме. Алгоритм по определенному критерию выбирает подмножество вершин, через которые может проходить кратчайший пути. Далее эти вершины могут обрабатываться параллельно (см. https://people.mpi-inf.mpg.de/~mehlhorn/ftp/ParallelizationDiikstra.pdf).

[0005] Недостатки известных решений заключаются в том, что в решении Giraph вершина в рамках супершага один раз принимает сообщения, и один раз отправляет. В случае применения массивно параллельных вычислительных систем, в ряде случаев, сильная система синхронизации препятствует полной загрузке всех процессоров и увеличивает время работы алгоритма.

[0006] Таким образом, в заявленном решении предлагается совершать множественные пересылки между вершинами за счет более слабой синхронизации.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

[0007] Решаемой технической проблемой с помощью заявленного изобретения является создание нового метода циклического распределенного асинхронного обмена сообщениями между узлами сети со слабой синхронизацией, для работы с большими графами.

[0008] Технический результат заключается в повышении эффективности и скорости передачи сообщений между узлами сети, что способствует быстрому решению прикладных задач в системе управления большими графами (FastGraph).

[0009] Заявленный результат достигается за счет компьютерно-реализуемого способа циклического распределенного асинхронного обмена сообщениями со слабой синхронизацией, выполняемого с помощью процессора и содержащего этапы, на которых:

a) определяют множество точек сетевого обмена сообщениями, где каждая точка представляет собой вычислительный узел;

b) формируют модель графа для обмена сообщениями между точками сетевого обмена, в котором вершинами являются точки сетевого обмена, а ребрами -факт отправки сообщений;

c) определяют точку сетевого обмена - координатора исполнения обмена сообщениями;

d) осуществляют отправку сообщений от точки координатора по меньшей мере одной точке сетевого обмена;

e) получают ответ от точки сетевого обмена, получившей сообщение на этапе d), причем упомянутый ответ содержит идентификаторы смежных точек сетевого обмена, в которые будут направлены сообщения от данной точки сетевого обмена, при этом упомянутая точка сетевого обмена формирует маршруты последующего обмена сообщениями;

f) на точке координаторе осуществляют учет сформированных маршрутов обмена сообщениями для каждой точки сетевого обмена графа, на основании сообщений от каждой точки сетевого обмена;

g) итеративно повторяют этапы e)-f) до того момента, пока точка координатор не сообщит, что точки сетевого обмена отсутствуют.

[0010] В одном из частных примеров выполнения способа каждая вершина содержит хранилище состояний, в котором содержится информация о признаке посещения.

[0011] Заявленный технический результат достигается также за счет системы циклического распределенного асинхронного обмена сообщениями со слабой синхронизацией, содержащей по меньшей мере один процессор и по меньшей мере одно средство памяти, которое хранит машиночитаемые инструкции, которые при их исполнении процессором реализуют вышеуказанный способ.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0012] Фиг. 1 иллюстрирует общий вид конической модели обмена сообщениями (пример реализации)

[0013] Фиг. 2 иллюстрирует блок-схему выполнения заявленного способа.

[0014] Фиг. 3 иллюстрирует пример вычислительной системы.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

[0015] На Фиг. 1 представлен пример реализации конической модели (100) обмена сообщениями. Точка (110) представляет узел - центр конуса, точка (150) - вершина конуса, точки (101) - (106) - узлы обмена данными, располагаемые на окружности конуса. В рамках реализации заявленного решения узлы конической модели обмениваются заданными типами сообщений, представленными в Таблице 1.

[0016] Необходимо отметить, что данный пример показывает лишь частную реализацию в виде конической архитектуры, которая может быть представлена различными вариациями графовой модели с сохранением заявленного функционала и основных вычислительных узлов решения (Таблица 2).

[0017] Узел сети, расположенный в вершине конуса (150) назначается координатором. С вершиной конуса (150) не ассоциируются никакие вершины (101-106, 110) графа. В координаторе храниться информация необходимая для выполнения обмена и работы (специфично для процесса).

[0018] Узел (110), расположенный в центре конуса, может посылать сообщение самому себе (т.е. центр конуса может быть на периферии). Каждое следующее семейство конусов в рамках одной вершины может быть инициировано только по окончании предыдущего. Детектировать окончание семейства конусов является функцией фреймворка. Это - единственная точка синхронизации (барьер) в конической модели.

[0019] Может быть несколько вершин конуса, осуществляющих операции параллельно. Порождаемые ими семейства конусов независимы друг от друга. В то же время они используют одни и те же точки, и обработка сообщений внутри точки происходит последовательно и синхронно.

[0020] На каждом из этапов исполнения алгоритма коническая модель обеспечивает взаимодействие между вычислительными узлами и координатором (150), в частности, отправления запросов, получение ответов, синхронизацию исполнения через ожидание ответов от всех узлов.

[0021] На Фиг. 2 представлена блок-схема предлагаемого способа (200) циклического распределенного асинхронного обмена сообщениями со слабой синхронизацией. На первом этапе (201) определяют множество точек сетевого обмена сообщениями, по которым на этапе (202) формируются модель графа для обмена сообщениями между точками сетевого обмена, в котором вершинами являются точки сетевого обмена, а ребрами - факт отправки сообщений.

[0022] На этапе (203) определяют точку сетевого обмена - координатора исполнения обмена сообщениями (150), т.е. вершину конуса - Pv, и инициирующие данные алгоритма dv для данной точки. Инициирующий конус в семействе конусов с помощью точки Pv имеет отличия от следующих в том, что он инициируется при помощи сообщения CRAM, в то время как последующие - при помощи сообщений СВМ.

[0023] На этапе (203) при выполнении инициализации выполняется создание координатора исполнения (150) и заданного количества вычислительных узлов - центров конусов для осуществления процесса обмена сообщениями. На данном этапе (203) также определяется алгоритм распределения (партиционирования) графа, предназначенный для формирования вычислительных узлов, поскольку каждый вычислительный узел отвечает за обработку части графа - порождает свое семейство конусов. Примером такого алгоритма может служить алгоритм вычисления хеш-функции идентификатора mod K (http://personal.kent.edu/~rmuhamma/Algorithms/MyAlgoritlmis/h

[0024] На узле-координаторе (150) функция алгоритма Av вычисляет узел - центр конуса (110) Рс и ассоциированные данные dvc, что составляет сообщение CRAM:

Av(dv) → (Рс, dvc).

[0025] Следующим шагом (204) является отправка координатором (150) сообщения CRAM точке сетевого обмена - центру конуса (110). Подробное описание шага представлено в разделе с описанием примера реализации способа на примере алгоритма CMMS-OUT.

[0026] На шаге (205) происходит следующее - на узле (110) (центр конуса) функция алгоритма Ас вычисляет список вершин (101) - (106) на периферии Pbn и ассоциированные данные dcbn, что составляет набор СВМ; также вычисляется САМ, в который включается список периферийных вершин (необходим для отслеживания завершения семейства конусов в узле-координаторе):

[0027] На шаге (206) происходит отправка САМ с данными из предыдущего пункта от точки сетевого обмена (центра конуса (110)) узлу координатору (150). Подробное описание данного шага представлено в разделе с описанием примера реализации способа на примере алгоритма CMMS-OUT.

[0028] На этапе (207) на точке координаторе (150) осуществляют учет сформированных маршрутов обмена сообщениями для каждой точки сетевого обмена графа (101)-(106), (110) на основании получаемых сообщений от каждой точки сетевого обмена. Принцип обработки зависит от процесса. Один из возможных принципов - вести две очереди - одна со списком всех точек сетевого обмена, которые необходимо посетить, а вторая очередь - со списком посещенных вершин.

[0029] На шаге (208) происходит проверка - посещены ли все точки сетевого обмена, завершены ли все параллельные работы. Если да, то обмен завершается. Если нет, происходит новая итерация и шаги (205-207) повторяются.

[0030] Далее рассмотрим пример реализации способа (200) на примере алгоритма CMMS-OUT.

[0031] Приведем пример реализации способа (200) на примере алгоритма CMMS-OUT (см. Фиг. 1). Алгоритм CMMS-OUT в конической модели описывает алгоритм поиска кратчайших путей (в классическом варианте однонаправленное), позволяющий находить кратчайшие пути и расстояния между некоторой вершиной (источником) и всеми остальными вершинами в графе - dist(n).

[0032] Алгоритм итеративный. Вершины делятся на непосещенные Q, посещенные и текущие С. Каждой вершине сопоставляется динамически (итеративно) обновляемое временное расстояние tdist(n) - минимальное из известных на данный момент расстояний от источника до данной вершины (предварительное расстояние). В посещенных вершинах tdist(n) = dist(n).

[0033] На первом шаге (итерации) tdist(s) = 0 для источника и tdist(n) = Infinity для всех остальных вершин n.

[0034] При каждом шаге (итерации) обновляется временное расстояние от текущих вершин до их инцидентов (вершин, к которым идут исходящие из них ребра), после чего текущие вершины объявляются посещенными. Следующие текущие вершины (следующие вершины для посещения) определяются условием:

С={ n | tdist(n) ≤ min { tdist(u) + w(u, z) | u in Q, u connected to z } }

Величина L = min { tdist(u) + w(u, z) | u in Q, u connected to z } (которая является частью условия С) далее называется пороговым значением (threshold).

[0035] Для удобства описания опишем поиск кратчайшего пути из двух точек сетевого обмена - из точки left (101) в точку right (106), то есть найти dist(right). Описание алгоритма будет соотнесено с этапами модели описанными выше (этапы из Фиг. 2).

[0036] Первые этапы модели одинаковы для всех алгоритмов (и для CMMS-OUT в частности), и подготавливают возможность работы алгоритмов. Этапы (201) - (203) выполняются аналогично описанному выше способу реализации.

[0037] В координаторе (150) ведется две приоритезированные очереди точек, одна с приоритетом по порогу (threshold), и вторая с приоритетом по минимальному весу пути - minPathWeight = min { tdist по вершинам точки }.

[0038] В вершине конуса (cone vertex) помещается координатор. С вершиной конуса не ассоциируются никакие вершины графа.

[0039] В работе алгоритма участвуют точки сетевого обмена (вершины) и вычислительные узлы (ВУ). Вычислительный узел ассоциирован с набором вершин - то есть каждый ВУ включает в себя несколько вершин (точек сетевого обмена). Каждая из вершин (точка сетевого обмена) ассоциирована ровно с одним ВУ.

[0040] С каждым ВУ ассоциировано хранилище состояний вершин ВУ (специфическое для процесса). В хранилище для каждой вершины ВУ хранятся:

предварительное расстояние (tdist);

признак посещения;

значение minCEW(u) = min { w(u, z) | u connected to z } - minimum connected edge weight, определяющее минимум веса исходящего ребра.

[0041] Также в хранилище хранится текущее консолидированное для всех вершин ВУ пороговое значение (threshold).

[0042] Как уже отмечалось выше на этапе (203) происходит определение координатора исполнения, а также происходит партиционирование - выбор заданного количества (X) вычислительных узлов (ВУ), которые будут определять построение семейства конусов и будут обеспечивать параллельное исполнение алгоритма.

[0043] Координатор не знает где располагается стартовая точка вычисления кратчайшего пути (left) и финальная точка nyra(right).

[0044] Для того чтобы найти стартовую точку left (для инициации алгоритма) координатор отправляет сообщение вычислительным узлам (ВУ) и получает ответ в каком вычислительном узле находится стартовая вершина.

[0045] Далее координатор на этапе (204) отправляет сообщение найденному ВУ в котором находится точка left.

[0046] На данном этапе (204) происходит отправка сообщения CRAM Init(left(101)) к точке сетевого обмена left (101) (начало пути). Вершина left (101) посещается (все пути к ней = 0). Это происходит при первой итерации алгоритма.

[0047] В дальнейшем координатор (150) (в дальнейших итерациях) на этапе (204) отправляет входные данные для этапа (205) - которые являются набором вершин, которые необходимо посетить в ходе выполнения этапа (205), которые распределены по различным ВУ, в парах с ассоциированным с вершиной весом пути к ней.

[0048] Таким образом координатор (150) может отправлять эти сообщения на этапе (204) нескольким ВУ параллельно, и соответственно шаги (205) - (206) будут выполняться в параллели для каждого ВУ. С каждым ВУ ассоциирован свой набор вершин.

[0049] На этапе (205) ВУ, получившая сообщение от координатора (150), формирует маршруты последующего обмена сообщениями. ВУ извлекает список смежных вершин и распределяет работу по добавлению этих вершин графа в очередь для посещения между соответствующим ВУ.

[0050] Каждый вычислительный узел должен рассчитать предел расстояния L для следующего шага и сообщить его координатору (150).

[0051] На этапе (205) происходит формирование на ВУ маршрутов последующего обмена сообщениями.

[0052] Для каждой точки сетевого обмена которая получила сообщение, отправленное на предыдущем этапе (204):

а) Ставится признак посещения (в хранилище состояний)

б) Выполняется макрошаг (Конус). Ассоциированная точка становится cone center.

в) Строится список вершин, куда идут ребра от данной вершины (incident nodes), в парах с ассоциированным с вершиной весом пути к ней (через текущую вершину). Применяется, при необходимости, фильтрация ребер и вершин.

г) По списку рассылается СВМ запроса порогового значения ThresholdRequest([(node, pathWeight)]). Сообщения агрегируются по ВУ, к которым принадлежат целевые вершины.

[0053] Внутри каждой вершины (точки сетевого обмена) по получении ThresholdRequest:

1. В хранилище состояний вершин для каждой из непосещенных вершин:

а) Если нет состояния (вершина не была ранее видима), добавляется объект состояния для данной вершины. При открытии новой вершины вершина считается непосещенной, tdist равен бесконечности, minCEW рассчитывается при инициализации состояния и далее не меняется.

б) производится обновление предварительных расстояний непосещенных вершин: если новое предварительное расстояние pathWeight меньше текущего tdist, новое становится текущим.

2. Вычисляется предложение по пороговому значению от ВУ: пороговое значение для всех непосещенных вершин из списка, принадлежащих данному вычислительному узлу (ВУ) (с использованием веса пути к ней и минимума веса исходящего ребра minCEW). Данная величина запоминается в хранилище.

[0054] После того как на этапе (205) сформированы предложения, они на этапе (206) отправляются координатору.

[0055] На этапе (206) на координатор высылается сообщение САМ VisitReport(thresholdOffer, minPathWeight) - информация по посещению ВУ, содержащая текущее пороговое значение для данного ВУ, взятое из хранилища, и со значением minPath Weight, равным минимуму tdist по вершинам ВУ.

[0056] Также на данном этапе от каждой вершины на координатор (150) отсылается сообщение CSM ThresholdOffer(thresholdOffer, minPath Weight) со значением предложения порогового значения thresholdOffer и со значением minPathWeight, равным минимуму tdist по вершинам ВУ.

[0057] На этапе (207) координатор (150) выбирает наименьший предел и дает команду вычислительным узлам посетить те вершин, которые попадают в данный предел.

[0058] Координатор вычисляет пороговое значение L и посещает те вершины, которые попали в данный предел.

[0059] На следующем этапе (207) на координаторе (150) происходит учет информации о сформированных маршрутах обмена сообщениями, а именно:

а) Координатор по получении САМ VisitReport обновляет приоритезированные очереди точек.

б) В координаторе все сообщения CSM ThresholdOffer агрегируются и вычисляется эффективное пороговое значение. Обновляются приоритезированные очереди.

[0060] Также на этапе (207) происходит вычисление вершин для следующего посещения - из приоритезированной очереди в координаторе выделяются все ВУ, имеющие непосещенные вершины, удовлетворяющие пороговому значению.

[0061] Также после учета сформированных маршрутов на этапе (207) происходит проверка окончания работы алгоритма: если в ранее полученных маршрутах имеется информация о вершине right, то завершить алгоритм и вернуть ассоциированное с right значение tdist как результат работы алгоритма. Если данной вершины не обнаружено, то происходит переход на этап 208.

[0062] На этапе (208) происходит проверка - есть ли новые вершины для посещения (информация об этом была сформирована на предыдущем этапе). Если новых вершин нет, то завершить алгоритм с результатом бесконечность (целевая вершина right не найдена, т.е. нет никакого пути, идущего к ней из left).

[0063] Если вершины имеются, то дальше происходит итеративный повтор этапов (204_ - (207) алгоритма способа (200).

[0064] Переход к этапу (204) осуществляется исходя их того, что по каждой из выбранных вершин рассылается сообщение CRAM VisitNodes(threshold), далее на этапе (205) каждый ВУ отбирает вершины, соответствующие пороговому значению. Эти вершины объявляются выбранными. Весами пути к ним являются их текущие значения tdist.

[0065] Этапы (206) - (208) выполняются до того момента, пока не будет найдена искомая вершина, или же не обнаружится что пути из точки left в точку right нет, или же алгоритм не остановится по другому критерию остановки - например максимальное количество итераций.

[0066] На Фиг. 3 представлен общий вид вычислительного устройства (300), пригодного для выполнения способа (200). Устройство (300) может представлять собой, например, сервер или иной тип вычислительного устройства, который может применяться для реализации заявленного способа.

[0067] В общем случае вычислительное устройство (300) содержит объединенные общей шиной информационного обмена один или несколько процессоров (301), средства памяти, такие как ОЗУ (302) и ПЗУ (303), интерфейсы ввода/вывода (304), устройства ввода/вывода (305), и устройство для сетевого взаимодействия (306).

[0068] Процессор (301) (или несколько процессоров, многоядерный процессор) могут выбираться из ассортимента устройств, широко применяемых в текущее время, например, компаний Intel™, AMD™, Apple™, Samsung Exynos™, MediaTEK™, Qualcomm Snapdragon™ и т.п. В качестве процессора (301) может также применяться графический процессор, например, Nvidia, AMD, Graphcore и пр.

[0069] ОЗУ (302) представляет собой оперативную память и предназначено для хранения исполняемых процессором (301) машиночитаемых инструкций для выполнение необходимых операций по логической обработке данных. ОЗУ (302), как правило, содержит исполняемые инструкции операционной системы и соответствующих программных компонент (приложения, программные модули и т.п.).

[0070] ПЗУ (303) представляет собой одно или более устройств постоянного хранения данных, например, жесткий диск (HDD), твердотельный накопитель данных (SSD), флэш-память (EEPROM, NAND и т.п.), оптические носители информации (CD-R/RW, DVD-R/RW, BlueRay Disc, MD) и др.

[0071] Для организации работы компонентов устройства (300) и организации работы внешних подключаемых устройств применяются различные виды интерфейсов В/В (304). Выбор соответствующих интерфейсов зависит от конкретного исполнения вычислительного устройства, которые могут представлять собой, не ограничиваясь: PCI, AGP, PS/2, IrDa, Fire Wire, LPT, COM, SATA, IDE, Lightning, USB (2.0, 3.0, 3.1, micro, mini, type C), TRS/Audio jack (2.5, 3.5, 6.35), HDMI, DVI, VGA, Display Port, RJ45, RS232 и т.п.

[0072] Для обеспечения взаимодействия пользователя с вычислительным устройством (300) применяются различные средства (305) В/В информации, например, клавиатура, дисплей (монитор), сенсорный дисплей, тач-пад, джойстик, манипулятор мышь, световое перо, стилус, сенсорная панель, трекбол, динамики, микрофон, средства дополненной реальности, оптические сенсоры, планшет, световые индикаторы, проектор, камера, средства биометрической идентификации (сканер сетчатки глаза, сканер отпечатков пальцев, модуль распознавания голоса) и т.п.

[0073] Средство сетевого взаимодействия (306) обеспечивает передачу данных устройством (300) посредством внутренней или внешней вычислительной сети, например, Интранет, Интернет, ЛВС и т.п. В качестве одного или более средств (306) может использоваться, но не ограничиваться: Ethernet карта, GSM модем, GPRS модем, LTE модем, 5G модем, модуль спутниковой связи, NFC модуль, Bluetooth и/или BLE модуль, Wi-Fi модуль и др.

[0074] Дополнительно могут применяться также средства спутниковой навигации в составе устройства (300), например, GPS, ГЛОНАСС, BeiDou, Galileo.

[0075] Представленные материалы заявки раскрывают предпочтительные примеры реализации технического решения и не должны трактоваться как ограничивающие иные, частные примеры его воплощения, не выходящие за пределы испрашиваемой правовой охраны, которые являются очевидными для специалистов соответствующей области техники.

Изобретение относится к области информационных технологий. Технический результат заключается в повышении эффективности и скорости передачи сообщений между вычислительными узлами сети. Технический результат достигается за счет этапов, на которых: a) определяют множество точек сетевого обмена сообщениями, где каждая точка представляет собой вычислительный узел; b) формируют модель графа для обмена сообщениями между точками сетевого обмена, в котором вершинами являются точки сетевого обмена, а ребрами - факт отправки сообщений; c) определяют точку сетевого обмена - координатора исполнения обмена сообщениями; d) осуществляют отправку сообщений от точки координатора по меньшей мере одной точке сетевого обмена; e) получают ответ от точки сетевого обмена, получившей сообщение на этапе d), причем упомянутый ответ содержит идентификаторы смежных точек сетевого обмена, в которые будут направлены сообщения от данной точки сетевого обмена, при этом упомянутая точка сетевого обмена формирует маршруты последующего обмена сообщениями; f) на точке координаторе осуществляют учет сформированных маршрутов обмена сообщениями для каждой точки сетевого обмена графа, на основании сообщений от каждой точки сетевого обмена; g) итеративно повторяют этапы e)-f) до того момента, пока точка координатор не сообщит, что точки сетевого обмена отсутствуют. 2 н. и 1 з.п. ф-лы, 3 ил., 2 табл.

1. Компьютерно-реализуемый способ циклического распределенного асинхронного обмена сообщениями со слабой синхронизацией, выполняемый с помощью процессора и содержащий этапы, на которых:

a) определяют множество точек сетевого обмена сообщениями, где каждая точка представляет собой вычислительный узел;

b) формируют модель графа для обмена сообщениями между точками сетевого обмена, в котором вершинами являются точки сетевого обмена, а ребрами - факт отправки сообщений;

c) определяют точку сетевого обмена - координатора исполнения обмена сообщениями;

d) осуществляют отправку сообщений от точки координатора по меньшей мере одной точке сетевого обмена;

e) получают ответ от точки сетевого обмена, получившей сообщение на этапе d), причем упомянутый ответ содержит идентификаторы смежных точек сетевого обмена, в которые будут направлены сообщения от данной точки сетевого обмена, при этом упомянутая точка сетевого обмена формирует маршруты последующего обмена сообщениями;

f) на точке координаторе осуществляют учет сформированных маршрутов обмена сообщениями для каждой точки сетевого обмена графа, на основании сообщений от каждой точки сетевого обмена;

g) итеративно повторяют этапы e)-f) до того момента, пока точка координатор не сообщит, что точки сетевого обмена отсутствуют.

2. Способ по п. 1, характеризующийся тем, что каждая вершина содержит хранилище состояний, в котором содержится информация о признаке посещения.

3. Система циклического распределенного асинхронного обмена сообщениями со слабой синхронизацией, содержащая по меньшей мере один процессор и по меньшей мере одно средство памяти, которое хранит машиночитаемые инструкции, которые при их исполнении процессором реализуют способ по любому из пп. 1, 2.