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

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

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

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