Мониторинг динамически меняющегося графа

Исследование ориентированных графов является корневой задачей во многих приложениях. Такое исследование имеет особую специфику тогда, когда граф моделирует сеть связи, в том числе сеть интернета и GRID. Узел сети имеет локальную информацию о сети: он «знает» только о дугах, выходящих из этой вершины, но «не знает», куда (в какие вершины) эти дуги ведут. Узлы сети обмениваются сообщениями, передаваемыми по сетевым связям, которые в графе изображаются как дуги и играют роль каналов передачи сообщений. Исследование графа базируется на его обходе, когда сообщение проходит по каждой дуге графа. Пока не пройдена какая-то дуга, нет уверенности, что она не ведёт в ещё не исследованную часть графа. Обычно рассматривается обход графа с помощью одного сообщения, циркулирующего в сети. Обход выполняется быстрее, если выполнять его параллельно: по сети одновременно циркулирует не одно, а множество сообщений. В данной работе рассматривается параллельное исследование сильно связного графа, целью которого является не просто обход графа, а сбор полной информации о графе в каждой его вершине. Вторая особенность работы – исследование динамически меняющегося графа: его дуги могут исчезать, появляться или менять свои конечные вершины. Предлагается алгоритм работы автоматов, который обеспечивает сбор полной информации о графе в каждой вершине графа.