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

Остовное дерево с минимальным весом

Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом 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 может использоваться с целью экономии на коммуникациях в самых разных задачах – таких как широковещательная передача и выбор лидера – путем отправки сообщений таких приложений по ребрам MST.

Кроме того, исследование проблемы MST и, в особенности, алгоритм MST в [5], стимулировали серьезные последующие работы. В частности, алгоритм из [5] включал различные техники, которые впоследствии получили широкое распространение в таких случаях, как широковещательные передачи, вопрос-ответ, кластерная координация и маршрутизация, протоколы квитирования, синхронизация и распределение по фазам. Хотя алгоритм достаточно понятен, он не так уж прост и не слишком поддается методам формальной верификации [11].