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

Задача создания распределенного алгоритма MST изучается с 1977 года, ей посвящены десятки статей. В 1983 году был опубликован фундаментальный алгоритм GHS [5] – первый алгоритм решения задачи MST со сложностью в сообщениях, равной <math>O(m + n \; log n)</math>. Эта статья имела огромное влияние на исследования в этой области и была удостоена премии Дейкстры 2004 года в области распределенных вычислений.

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

Нижняя граница сложности в сообщениях <math>\Omega (m + n \; log n)</math> при построении MST наблюдается также при решении задачи нахождения произвольного остовного дерева графа. Однако для конкретных топологий графов может оказаться проще найти произвольное остовное дерево, чем минимальное. В случае полного графа для построения MST требуется <math>\Omega (n^2) \; </math> сообщений [8], тогда как произвольное остовное дерево может быть построено за <math>O(n \; log n)</math> сообщений [7].

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