О распределённых вычислениях в синхронных сетях с неизвестной топологией Хузиев Ильнур Масхудович

Короткий опис

Хузиев, Ильнур Масхудович.
О распределённых вычислениях в синхронных сетях с неизвестной топологией : диссертация ... кандидата физико-математических наук : 01.01.09 / Хузиев Ильнур Масхудович; [Место защиты: Московский физико-технический институт (национальный исследовательский университет)]. - Москва, 2019. - 89 с. : ил.
Оглавление диссертациикандидат наук Хузиев Ильнур Масхудович
Введение
Связь с работами других авторов
1. Глава 1. Определения
Протокол вычисления высоты
Метод синхронизации часов
2. Глава 2. Быстрый протокол выбора лидера
2.1 Неформальное описание протоколов
2.2 Слабо-корректный протокол передачи минимального идентификатора
Кодирование идентификаторов
Описание протокола
Слабая корректность протокола
Улучшенная оценка времени работы
Построение остовного дерева
2.3 Корректные протоколы
Описание корректного протокола
Корректность комбинированного протокола
3. Глава 3. Быстрый поиск объектов, заданных топологическими свойствами
3.1 Быстрое распространение информации об остовном дереве
Протокол поиска мостов
3.2 Поиск антиподальной вершины в симметричном графе Кэли над булевым кубом
3.2 Поиск антиподальной вершины в симметричном графе Кэли над булевым кубом
4. Глава 4. Протокол построения остовного дерева с малой коммуникационной сложностью
4.1 Оптимальные протоколы при известной оценке размера сети
Протокол при равномерной оценке размера сети
Протокол при неравномерной оценке размера сети
4.2. Субоптимальные по трафику протоколы
Описание неограниченного протокола
Корректность описания протокола
Оценка траффика протокола
4.3. Вероятностные протоколы для анонимных сетей
Протокол с неравномерной оценкой размера сети
Слабо-корректные протоколы
Заключение
Приложения
А. О нижних оценках времени и трафика
Б. О невозможности разрушить симметрию в анонимных сетях
Список литературы