Распределенная коммуникационная сложность построения остовного дерева

Рассматривается задача построения остовного дерева в синхронизированной сети с неизвестной топологией. Даны нижние и верхние оценки на сложность протоколов построения остовного дерева в различных постановках: для детерминированных и вероятностных протоколов, для сетей с различающимися узлами и для анонимных сетей. Приведены субоптимальные протоколы, в которых мультипликативный разрыв от нижней оценки может быть сколь угодно медленно растущей функцией от числа вершин в сети.