Быстрые протоколы выбора лидера и построения остовного дерева в распределенной сети

Рассматриваются задачи выбора лидера и построения остовного дерева в синхронизированной сети с неизвестной топологией. Анализ протоколов проводится в предположении, что узлы сети различимы, но размер идентифицирующей узел информации может быть сколь угодно велик. Построены быстрые протоколы для этих задач, которые работают за время $O(D\log L+L)$, где $L$ – размер наименьшего идентификатора, а $D$ – диаметр сети.