Распределенные алгоритмы для минимальных остовных деревьев: различия между версиями

Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом G = (V, E), где |V| = n, |E| = m. Каждая вершина V представляет процессор неограниченной вычислительной мощности; процессоры имеют уникальные идентификационные номера и общаются друг с другом посредством дуг из E, по которым они пересылают друг другу сообщения. Кроме того, каждой дуге <math>e \in E</math> присвоен вес w(e), известный процессорам в концевых точках e. Таким образом, каждому процессору известны инцидентные ему дуги и их веса, однако никакой другой информации о графе G он не имеет. Сеть является [[асинхронная сеть|асинхронной]]: каждый процессор работает на произвольной скорости, не зависящей от скорости других процессоров. Процессор может «проснуться» спонтанным образом либо в результате получения сообщения от другого процессора. В сети не имеется конфликтов; каждое посланное сообщение прибывает по месту назначения с конечной, но произвольной задержкой. [[распределенный алгоритм|Распределенный алгоритм]] A для графа G представляет собой множество локальных алгоритмов, по одному для каждого процессора G, включающих команды для отправки и получения сообщений по ребрам графа. Предположим, что алгоритм A завершает работу (то есть все локальные алгоритмы в конечном итоге завершают работу); тогда его ''сложность в сообщениях'' представляет собой полное число сообщений, переданных при любом варианте исполнения алгоритма, в наихудшем случае. ''Временная сложность'' алгоритма представляет собой время исполнения в наихудшем случае, в предположении, что циклы процессора требуют пренебрежимо малого времени, а нормализованные задержки сообщений не превышают 1 единицы измерения.

[[минимальное остовное дерево|Минимальное остовное дерево]] (MST) графа G представляет собой подмножество E' множества дуг E, такое, что граф T = (V, E') представляет собой дерево (связное и ациклическое), а его общий вес <math>w(E') = \sum_{e \in E'} w(e)</math> является насколько возможно малым. Вычисление MST является центральной задачей комбинаторной оптимизации; оно ведет свою историю еще с 1926 года [2]. В работе [12] сведены воедино свойства, классические результаты, варианты применения и последние достижения исследователей в этой области.

Целью задачи создания распределенного алгоритма для минимальных остовных деревьев является разработка такого распределенного алгоритма A, который всегда завершается и дает в результате минимальное остовное дерево (MST) T для графа G. В конце исполнения каждый процессор знает, какая из инцидентных ему дуг входит в T и какая – нет (т.е. процессор записывает соответствующие инцидентные дуги в локальный выходной регистр). Стоит отметить, что в распределенной версии алгоритма MST коммуникационная сеть решает задачу, входным параметром которой является она сама. Это одно из фундаментальных свойств сетевых алгоритмов.

Нетрудно заметить, что в случае, если все дуги имеют разные веса, минимальное остовное дерево является единственным. В силу предположения, что все процессоры имеют уникальные идентификаторы, можно предположить, что все веса дуг различны: если веса двух дуг равны, можно выбрать нужную, используя идентификаторы процессоров на концевых точках дуг. Наличие уникального MST способствует разработке распределенных алгоритмов, так как процессоры могут локально выбирать дуги, принадлежащие уникальному MST. Заметим, что если процессоры не имеют уникальных идентификаторов, а веса дуг не являются различными, не существует детерминированного распределенного алгоритма нахождения минимального остовного дерева (и просто остовного дерева), поскольку в таком случае может оказаться невозможным разрушить симметрию графа – например, в случае цикла, в котором веса всех дуг равны.

Нетрудно увидеть, что любой распределенный MST-алгоритм должен иметь сложность в сообщениях, равную <math>\Omega (m) </math> (интуитивно понятно, что по каждой дуге должно пройти хотя бы одно сообщение). В [3, 4] было показано, что нижней границей сложности в сообщениях служит <math>\Omega (n log n)</math>. Таким образом, алгоритм GHS является оптимальным по сложности в сообщениях.

Временная сложность алгоритма GHS составляет O(n log n). В [1] предложен механизм улучшения временной сложности до O(n) при сохранении оптимальной сложности в сообщениях – O(m + n log n). Очевидно, что построение остовного дерева требует времени <math>\Omega (D)</math>, где D – диаметр графа. В случае минимального остовного дерева временная сложность может зависеть и от других параметров графа. К примеру, в силу необходимости потока информации между процессорами, входящими в цикл (как это бывает при построении MST), по крайней мере одна дуга цикла должна быть исключена из MST. В случае, если разрешены сообщения неограниченного размера, MST можно легко построить за время O(D), путем сбора данных о топологии графа и весах дуг в корневом процессоре. Задача становится более сложной в реалистичной модели, в которой сообщения имеют размер O(log n), а вес дуги может быть отправлен отдельным сообщением. Если число сообщений не имеет значения, без потери общности можно предположить, что модель является синхронной. Сведения об алгоритмах, близких к оптимальным по времени, и нижних границах см. в [10] и соответствующих ссылках.

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