Распределенные алгоритмы для минимальных остовных деревьев
Ключевые слова и синонимы
Остовное дерево с минимальным весом
Постановка задачи
Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом G = (V, E), где |V| = n, |E| = m. Каждая вершина V представляет процессор неограниченной вычислительной мощности; процессоры имеют уникальные идентификационные номера и общаются друг с другом посредством ребер из E, по которым они пересылают друг другу сообщения. Кроме того, каждому ребру [math]\displaystyle{ e \in E }[/math] присвоен вес w(e), известный процессорам в концевых точках e. Таким образом, каждому процессору известны инцидентные ему ребра и их веса, однако никакой другой информации о графе G он не имеет. Сеть является асинхронной: каждый процессор работает на произвольной скорости, не зависящей от скорости других процессоров. Процессор может «проснуться» спонтанным образом либо в результате получения сообщения от другого процессора. В сети не имеется конфликтов; каждое посланное сообщение прибывает по месту назначения с конечной, но произвольной задержкой. Распределенный алгоритм A для графа G представляет собой множество локальных алгоритмов, по одному для каждого процессора G, включающих команды для отправки и получения сообщений по ребрам графа. Предположим, что алгоритм A завершает работу (то есть все локальные алгоритмы в конечном итоге завершают работу); тогда его сложность в сообщениях представляет собой полное число сообщений, переданных при любом варианте выполнения алгоритма, в наихудшем случае. Временная сложность алгоритма представляет собой время выполнения в наихудшем случае, в предположении, что циклы процессора требуют пренебрежимо малого времени, а нормализованные задержки сообщений не превышают 1 единицы измерения.
Минимальное остовное дерево (MST) графа G представляет собой подмножество E' множества ребер E, такое, что граф T = (V, E') представляет собой дерево (связное и ациклическое), а его общий вес [math]\displaystyle{ w(E') = \sum_{e \in E'} w(e) }[/math] является насколько возможно малым. Вычисление MST является центральной задачей комбинаторной оптимизации; оно ведет свою историю еще с 1926 года [2]. В работе [12] сведены воедино свойства, классические результаты, варианты применения и последние достижения исследователей в этой области.
Целью задачи создания распределенного алгоритма для минимальных остовных деревьев является разработка такого распределенного алгоритма A, который всегда завершается и дает в результате минимальное остовное дерево (MST) T для графа G. В конце выполнения каждый процессор знает, какая из инцидентных ему ребер входит в T и какая – нет (т.е. процессор записывает соответствующие инцидентные ребра в локальный выходной регистр). Стоит отметить, что в распределенной версии алгоритма MST коммуникационная сеть решает задачу, входным параметром которой является она сама. Это одно из фундаментальных свойств сетевых алгоритмов.
Нетрудно заметить, что в случае, если все ребра имеют разные веса, минимальное остовное дерево является единственным. В силу предположения, что все процессоры имеют уникальные идентификаторы, можно предположить, что все веса ребер различны: если веса двух ребер равны, можно выбрать нужное, используя идентификаторы процессоров на концевых точках ребер. Наличие уникального MST способствует разработке распределенных алгоритмов, так как процессоры могут локально выбирать ребра, принадлежащие уникальному MST. Заметим, что если процессоры не имеют уникальных идентификаторов, а веса ребер не являются различными, не существует детерминированного распределенного алгоритма нахождения минимального остовного дерева (и просто остовного дерева), поскольку в таком случае может оказаться невозможным разрушить симметрию графа – например, в случае цикла, в котором веса всех ребер равны.
Основные результаты
Задача создания распределенного алгоритма MST изучается с 1977 года, ей посвящены десятки статей. В 1983 году был опубликован фундаментальный алгоритм GHS [5] – первый алгоритм решения задачи MST со сложностью в сообщениях, равной O(m + n log n). Эта статья имела огромное влияние на исследования в этой области и была удостоена премии Дейкстры 2004 года в области распределенных вычислений.
Нетрудно увидеть, что любой распределенный MST-алгоритм должен иметь сложность в сообщениях, равную [math]\displaystyle{ \Omega (m) }[/math] (интуитивно понятно, что по каждому ребру должно пройти хотя бы одно сообщение). В [3, 4] было показано, что нижней границей сложности в сообщениях служит [math]\displaystyle{ \Omega (n log n) }[/math]. Таким образом, алгоритм GHS является оптимальным по сложности в сообщениях.
Нижняя граница сложности в сообщениях [math]\displaystyle{ \Omega (m + n log n) }[/math] при построении MST наблюдается также при решении задачи нахождения произвольного остовного дерева графа. Однако для конкретных топологий графов может оказаться проще найти произвольное остовное дерево, чем минимальное. В случае полного графа для построения MST требуется [math]\displaystyle{ \Omega (n^2) }[/math] сообщений [8], тогда как произвольное остовное дерево может быть построено за O(n log n) сообщений [7].
Временная сложность алгоритма GHS составляет O(n log n). В [1] предложен механизм улучшения временной сложности до O(n) при сохранении оптимальной сложности в сообщениях – O(m + n log n). Очевидно, что построение остовного дерева требует времени [math]\displaystyle{ \Omega (D) }[/math], где D – диаметр графа. В случае минимального остовного дерева временная сложность может зависеть и от других параметров графа. К примеру, в силу необходимости потока информации между процессорами, входящими в цикл (как это бывает при построении MST), по крайней мере одно ребро цикла должно быть исключено из MST. В случае, если разрешены сообщения неограниченного размера, MST можно легко построить за время O(D), путем сбора данных о топологии графа и весах ребер в корневом процессоре. Задача становится более сложной в реалистичной модели, в которой сообщения имеют размер O(log n), а вес ребра может быть отправлен отдельным сообщением. Если число сообщений не имеет значения, без потери общности можно предположить, что модель является синхронной. Сведения об алгоритмах, близких к оптимальным по времени, и нижних границах см. в [10] и соответствующих ссылках.
Применение
Задача создания распределенного алгоритма MST имеет важное теоретическое и практическое значение, поскольку MST может использоваться с целью экономии на коммуникациях в самых разных задачах – таких как широковещательная передача и выбор лидера – путем отправки сообщений таких приложений по ребрам MST.
Кроме того, исследование проблемы MST и, в особенности, алгоритм MST в [5], стимулировали серьезные последующие работы. В частности, алгоритм из [5] включал различные техники, которые впоследствии получили широкое распространение в таких случаях, как широковещательные передачи, вопрос-ответ, кластерная координация и маршрутизация, протоколы квитирования, синхронизация и распределение по фазам. Хотя алгоритм достаточно понятен, он не так уж прост и не слишком поддается методам формальной верификации [11].
Открытые вопросы
В этой области остается множество открытых вопросов. Хотя асимптотически жесткая граница сложности по сообщениям O(m + n log n) для задачи нахождения MST в графах общего вида известна, проблема нахождения фактических ограничений остается нерешенной. Однако для остовных деревьев общего вида, в отличие от минимальных, существуют константы меньшей величины [6].
Как упоминалось выше, в работе [10] и содержащихся в ней ссылках можно найти сведения об алгоритмах, близких к оптимальным по времени, и нижних границах. Задача достижения оптимальной временной сложности остается нерешенной. Кроме того, в синхронной модели для наложенных сетей, в которых все процессоры напрямую связаны друг с другом, MST может быть построено за сублогарифмическое время, а именно – за O(log log n) эпизодов коммуникации [9], и нижняя граница для него неизвестна.
См. также
Литература
1. Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems (detailed summary). In: Proc. of the 19th Annual ACM Symposium on Theory of Computing, pp. 230-240. ACM, USA (1987)
2. Boruvka, O.: Otakar Boruvka on minimum spanning tree problem (translation of both the 1926 papers, comments, history). Disc. Math. 233, 3-36 (2001)
3. Burns, J.E.: A formal model for message-passing systems. Indiana University, Bloomington,TR-91, USA (1980)
4. Frederickson, G., Lynch, N.: The impact of synchronous communication on the problem of electing a leader in a ring. In: Proc. of the 16th Annual ACM Symposium on Theory of Computing, pp. 493-503. ACM, USA (1984)
5. Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Prog. Lang. Systems 5(1), 66-77 (1983)
6. Johansen, K.E., Jorgensen, U.L., Nielsen, S.H.: A distributed spanning tree algorithm. In: Proc. 2nd Int. Workshop on Distributed Algorithms (DISC). Lecture Notes in Computer Science, vol. 312, pp. 1-12. Springer, Berlin Heidelberg (1987)
7. Korach, E., Moran, S., Zaks, S.: Tight upper and lower bounds for some distributed algorithms for a complete network of processors. In: Proc. 3rd Symp. on Principles of Distributed Computing (PODC), pp. 199-207. ACM, USA (1984)
8. Korach, E., Moran, S., Zaks, S.: The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. In: Proc. 4th Symp. on Principles of Distributed Computing (PODC), pp. 277-286. ACM, USA (1985)
9. Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput. 35(1), 120-131 (2005)
10. Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. Distrib. Comput. 18(6), 453^60 (2006)
11. Moses, Y., Shimony, B.: A new proof of the GHS minimum spanning tree algorithm. In: Distributed Computing, 20th Int. Symp. (DISC), Stockholm, Sweden, September 18-20, 2006. Lecture Notes in Computer Science, vol.4167, pp. 120-135. Springer, Berlin Heidelberg (2006)
12. Wu, B.Y., Chao, K.M.: Spanning Trees and Optimization Problems (Discrete Mathematics and Its Applications). Chapman Hall, USA (2004)
