Архив выступлений: 2015-2016 учебный год, весенний семестр

И. Б. Бурдонов, А. С. Косачев (ИСП РАН).
«Исследование ориентированного графа коллективом неподвижных автоматов».

Аннотация доклада.

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

Первый алгоритм решает задачу обхода графа и выполняет разметку графа с помощью изменения состояний автоматов в вершинах. Время работы алгоритма O(n/k+d), где n – число вершин графа, d – диаметр графа, а k – «ёмкость» дуги как число сообщений, которые могут одновременно передаваться по дуге.

Второй алгоритм, используя эту разметку, решает задачу параллельного вычисления значения заданной функции от мультимножества значений, записанных в вершинах графа. Разметка графа не зависит от той функции, которая будет вычисляться. Это означает, что разметка графа выполняется один раз, после чего может многократно использоваться для вычисления различных функций. Время работы алгоритма O(d).

Эти алгоритмы предназначены для работы на статическом (не меняющемся) графе. Далее рассматривается случай динамически меняющегося графа: его дуги могут исчезать, появляться или менять свои конечные вершины. Если дуга существует и не меняется достаточно долго, чтобы по ней могло пройти хотя бы одно сообщение, то такую дугу будем называть «долгоживущей». Для того чтобы можно было исследовать такой граф, недостаточно потребовать, чтобы граф был сильно-связным в каждый момент времени. Однако достаточно, чтобы в каждый момент времени «долгоживущие» дуги порождали сильно-связный суграф.

Предлагается алгоритм мониторинга динамически меняющегося графа, задача которого сбор полной информации о графе в каждой его вершине. Понятно, что если граф постоянно меняется, то мы не можем гарантировать, что описания текущего состояния всех его дуг отражены во всех его вершинах: сообщения о последних изменениях дуг просто «не дошли» до некоторых вершин. Поэтому требуется только, чтобы через время T0 после изменения дуги все вершины графа «узнали» об этом или более позднем изменении дуги. Если после данного изменения дуга больше не меняется, по крайней мере, в течение времени T0, то во всех вершинах графа будет одинаковое (и верное) описание этой дуги. Время работы алгоритма T0 = O(d).

Для динамически меняющегося графа также разработаны алгоритмы разметки графа и параллельного вычисления функции. Время работы алгоритма разметки O(n). Время вычисления функции O(n2/w), где wn-1 – задаваемый извне параметр, которому прямо пропорциональны размер памяти автомата и сообщений в алгоритме вычисления функции.