Как работает алгоритм обхода зависимостей между процессами в больших вычислительных системах?

Возможно, имелся в виду алгоритм обхода графа, который используется для параллельного тестирования больших автоматных моделей. 1

Основная задача обходчика — вычисление маршрута из заданной вершины графа в какую-либо вершину, из которых выходят ещё не пройденные дуги. 1

Алгоритм включает следующие функции: 1

1. Инициализация обходчика. 1 Устанавливаются параметры обхода, передаётся начальная вершина графа и список допустимых в ней стимулов. 1
2. Вычисление маршрута в графе и подаваемого стимула. 1 Обходчик вычисляет путь из указанной вершины графа в вершину, в которой есть ещё не пройденные дуги, а также стимул одной из этих дуг. 1
3. Добавление в граф пройденной дуги. 1 При этом указывается, получена ли эта дуга синхронизатором от другого процесса или пройдена локально. 1 Вместе с дугой передаётся информация о числе стимулов, допустимых в конечной вершине дуги. 1
4. Получение списка дуг, пройденных локально. 1 Возвращается список дуг, пройденных локальным обходчиком с момента последнего вызова этой функции (или начала работы процесса тестовой системы). 1

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

Алгоритм позволяет выявлять скрытые информационные зависимости в программе и определять циклы, которые могут быть исполнены параллельно. 5