БЫСТРЫЕ ПРОТОКОЛЫ ВЫБОРА ЛИДЕРА И ПОСТРОЕНИЯ ОСТОВНОГО ДЕРЕВА В РАСПРЕДЕЛЕННОЙ СЕТИ

摘要

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