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

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

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