О распределённых вычислениях в синхронных сетях с неизвестной топологией тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Хузиев Ильнур Масхудович

• Хузиев Ильнур Масхудович
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Хузиев Ильнур Масхудович

Введение

Связь с работами других авторов

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. Вероятностные протоколы для анонимных сетей

Протокол с неравномерной оценкой размера сети

Слабо-корректные протоколы

Заключение

Приложения

А. О нижних оценках времени и трафика

Б. О невозможности разрушить симметрию в анонимных сетях

Список литературы

Введение диссертации (часть автореферата) на тему «О распределённых вычислениях в синхронных сетях с неизвестной топологией»

Введение

В данной работе исследуются распределённые вычислительные сети. Тема алгоритмов, в которых более одного вычислительного узла, всесторонне изучается уже более полувека: известно большое число различных задач, постановок и подходов.

Как правило, при постановке задачи топология сети, в которой её предполагается решать, является фиксированной и известной всем узлам сети, что вполне естественно, так как реальные компьютерные сети проектируются в соответствии с некоторой архитектурой и практическими требованиями, имеют механизмы центрального управления и синхронизации действий.

Но возможны и другие типы сетей, которые возникли спонтанно (например, в системах беспроводной связи с равноправными участниками) или без общего плана (например, объединение двух централизованных сетей). В таких случаях узлы не знают топологии всей сети. Что приводит к невозможности использования напрямую методов, опирающихся на это знание.

Целью данного исследования является, во-первых, формализация понятия сети с неизвестной топологией. И, во-вторых, нахождение оценок на время и траффика (трафиком мы называем суммарное число непустых сообщений, передаваемых по связям в ходе работы протокола) для протоколов, которые сводят сети с неизвестной топологией к сетям с известной топологией.

Одной из базовых задач при определении топологии является выбор лидера1 и построение остовного дерева2. Если сеть имеет возможность построить плотную нумерацию узлов (все узлы имеют уникальный номер от 1 до числа узлов), то она может и выбрать лидера (например, объявить лидером узел с номером 1). Таким образом возможность выбора лидера является необходимым условием возможности полного определения топологии.

1 . Лидером называется узел, который «знает» что он лидер, а остальные узлы «знают» каждый про себя, что они не являются лидерами. Формальные определения будут ниже по тексту. Задача выбора лидера ещё часто называют задачей разрушения симметрии, имея в виду что в начальном состоянии все узлы равноправны.

2 Напомним, что остовным деревом связного графа называется ацикличный связный подграф, содержащий все вершины.

Вопросы о самодиагностике сети и обнаружении других свойств вполне естественно возникают в тех сетях, которые создаются не по заранее построенному плану, а хаотично, либо под-

V /ч V

вержены высокой изменчивости. С практической точки зрения некоторые условия, в которых результаты работы применимы, выглядят экзотическими (например, все устройства заведомо имеют уникальные «заводские» номера, причём их длина мала). Тем не менее задачи выбора лидера или установления свойств топологии спонтанно возникшей сети могут возникать, но в реально используемых сетях используются пакеты относительно большого объема (как правило не составляет проблем подписать пакет уникальным идентификатором узла). Можно интерпретировать протоколы с высокой адаптивностью, которые строятся в этой работе, как протоколы для многопроцессорных систем с общей памятью. Но в рамках данной работы такой интерпретации (алгоритмы для «акторной» модели параллельных алгоритмов) не делалось. Несмотря на это, с теоретической точки зрения модель представляет несомненный интерес в виду 1) общности постановки 2) хорошего варианта достаточно простой, но и не тривиальной, базовой модели, в которой для многих задач удаётся найти хорошие оценки.

Работа организована следующим образом.

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

Главный класс сетей, в которых возможен выбор лидера, - это сети, узлы которых имеют уникальные идентификаторы. Данная модель по сути является самой слабой из тех, в которых узлы не находятся в заведомо различных условиях и не имеют никаких дополнительных знаний о сети (кроме факта уникальности идентификаторов).

В приложении Б показано3, что если в сети идентификаторы не уникальны, то даже рандомизированные алгоритмы не могут выбрать лидера за гарантированно конечное время.

3 Этот результат несложен и, кажется, знаком всем, кто занимается этими вопросами. Но найти формального опубликованного доказательства не удалось. Для полноты изложения доказательство и приводится в приложении.

В главе 2 рассматривается задача перехода от сети с уникальными идентификаторами к сети с лидером. Строится протокол для быстрого выбора лидера в рассматриваемой модели, время работы этого протокола ограничено 0(й \ogL + ¿), где й - диаметр графа, а Ь - минимальная длина ключа в сети. Нижняя оценка на время выбора лидера 0(й + V) (см приложение А). Протоколы, известные ранее и адаптированные к нашей модели, могли предложить в лучшем случае 0(0Ь + V). Стоит отметить, что нижние оценки получены из очень простых информационных оценок.

После выбора лидера сети следующим логичным шагом является построение остовного дерева с корнем. Это не полная информация о топологии сети, но важная её часть. Для некоторого класса задач этой информации достаточно для оптимального решения. Также наличие остовного дерева позволяет с использованием его обхода построить плотную нумерацию узлов. Такая нумерация индуцирует нумерацию рёбер парами связанных узлов. Если соседние узлы обменяются своими номерами, то они узнают «номера» смежных рёбер. Для сбора полной информации о сети достаточно «отправить» информацию о смежных рёбрах в узел-лидер. После чего лидер может распространить матрицу смежности между всеми узлами.

В главе 3 рассматриваются две задачи, в которых требуется найти в сети объекты, заданные через свойства топологии сети. В разделе 3.1 рассматривается задача плотной нумерации и поиска мостов. В разделе 3.2 рассматривается задача поиска антиподальной вершины в симметричном графе Кэли над группой булева куба. Данные задачи интересны тем, что их можно решать, не находя полной информации о топологии сети, то есть приведённые протоколы быстрее «тривиального» подхода через аккумулирование всей матрицы смежности в некотором узле.

В разделе 3.1 приводится протокол быстрой нумерации через обход в ширину и распространение полной информации об остовном дереве по всем узлам сети. Время работы построенного протокола линейное по размеру сети, что соответствует нижним оценкам в худшем случае. Основным инструментом в использованном протоколе является идея префиксного вычисления по данным поддеревьев. Этот же приём позволяет за линейное время находить все мосты и распространять эту информацию по всей сети. Последний результат также улучшает ранее известный результат (так как не требует подписи всех сообщений номером узла) в задаче поиска мостов.

Заметим, ещё раз, что в разделе 3.1 также предъявляется протокол, который позволяет перейти от сетей с лидером к плотно-нумерованным сетям. Дополнив это простым шагом по распространению информации о всех существующих рёбрах (после нумерации узлов можно рёбра занумеровать парой чисел - номерами узлов), получаем сеть с полной информацией о топологии. Таким образом возможность выбора лидера в сети является достаточным условием перехода к сетям с полной топологией.

В главе 4 рассматривается задача перехода от сети с уникальными идентификаторами к сети с лидером и локальным остовным деревом (каждый узел знает своего родителя в дереве и непосредственных потомков) с точки зрения минимизации количества переданных бит.

В разделе 4.1 показано, что при наличии дополнительной информации о сети - оценки размера сети - для данной задачи существуют оптимальные по трафику протоколы. Развитием идей из этих утверждений удаётся доказать теорему 4.2.1, которая даёт верхнюю оценку, отличающуюся от нижней с точностью до неограниченного, но сколь угодно медленно растущего, мультипликативного множителя. Стоит заметить, что и в данном случае нижняя оценка получена тривиальным информационным рассуждением.

Итак, основные результаты работы состоят в следующем:

• Получены необходимые и достаточные условия для возможности перехода от сети с неизвестной топологией к сети с известной (возможность выбора лидера).

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

• Построен эффективный (совпадает с нижней оценкой в худшем случае) по времени работы протокол построения плотной нумерации и выбора остовного дерева.

• Показано, что при наличии остовного дерева легко найти и распространить полную информацию о топологии сети.

• Использованная для построения основного дерева техника позволяет улучшить ранее известные результаты для задачи поиска мостов.

• Рассмотрена постановка с минимизацией трафика (вместо времени) в том же семействе сетей. Для неё получена верхняя оценка очень близкая к тривиальной нижней оценке.

• Рассмотрена задача поиска антиподальной вершины в симметричных графах Кэли над группой булева куба. Построен полиномиальный протокол решения. При этом «тривиальный» подход требует экспоненциального времени.

Полученные результаты достаточно подробно раскрывают структуру задачи.

Связь с работами других авторов

В качестве обзорных материалов по теме распределённых вычислений можно порекомендовать [6, 8].

Одной из проблем изучения распределённых вычислений является многообразие рассматриваемых моделей, что ведёт к сложности сравнения результатов. Одним из ключевых свойств используемой модели сети является различие между асинхронными и синхронными сетями4. Формулировки задач в сетях с неполной информацией о топологии более характерны для асинхронных моделей, но их сравнение с синхронными моделями не вполне корректно.

Хотелось бы отметить, что одним из полезных свойств используемого в данной работе формализма является сама возможность сравнения достаточно сильно отличающихся моделей за счёт их сведения к более «базовой».

Другой важной особенностью моделей является модель сообщений. Часто оптимизируемой величиной является число сообщений, при этом размер самих сообщений может быть большим. Стандартным является использование подписанных сообщений5.

Всё это осложняет сравнение результатов. Тем не менее постараемся привести наиболее релевантные и близкие работы.

4 Многие результаты из данной работы переносимы на асинхронные модели: протоколы можно переформулировать, чтобы они по-прежнему находили лидеров, строили мосты и т.п. Но оценки на время теряют свою корректность. Результаты из главы 5 не переносимы на асинхронные модели.

5 То есть к каждому сообщению можно дополнительно дописать logV бит, обычно это номер некоторого узла. Использование таких подписей вполне согласуется с используемым на практике протоколами сетевого обмена.

Одним из часто используемых «строительных блоков» в наших протоколах является эхо протокол и его модификации. Он описан, например, в работе Перльман [7].

В работе [3] рассматривается задача разрушения симметрии в кольцевых сетях (разрушение сети по своей сути эквивалентно выбору лидера). Следуя идеям этой работы, мы различаем разные типы завершения протоколов (подробно об этом в первой главе). Использованный в [3] термин message-terminating protocol соответствует термину слабо-корректные протоколы из данной работы, а термин processor-terminating protocol из [3] соответствует корректным протоколам из данной работы. Термин сильно-корректный протокол не имеет прямого аналога в [3]. В этой работе авторы установили близкие верхние и нижние оценки, связывающие синхронизированную коммуникационную сложность и обычную детерминированную коммуникационную сложность в предположении, что время работы протокола ограничено полиномом от числа булевых переменных у участников протокола.

Стоит заметить, что минимизация трафика протокола очень близка к понятию коммуникационной сложности - в обоих случаях измеряется объём передаваемой информации. Чтобы разделить случай «простой» коммуникационной сложности функции (в её определении участвует только два узла) от оценки объема передаваемых сообщений в сложной сети используется термин распределённая коммуникационная сложность.

Относительно оценок на распределённую коммуникационную сложность выбора лидера известны следующие результаты. Для кольцевых сетей в [5] доказана нижняя оценка log V) для числа сообщений в протоколе, решающем задачу выбора лидера (уникального узлав сети). В работе [2] получена такая же нижняя оценка для решения задачи достижения консенсуса (все узлы должны выдать одинаковый бит) в кольцевой сети. Нетрудно видеть, что эти задачи решаются с дополнительными 0(V) сообщениями, если в кольцевой сети с заданными ориентациями связей в каждом узле (по и против часовой стрелки) построено остовное дерево (т.е. удалено одно ребро).

Известны нижние оценки времени распределённого построения кратчайшего остовного дерева [1, 8], однако они используют другую модель (априорная плотная нумерация и подписанные сообщения).

В разделе 3.1 мы рассматриваем задачу поиска мостов. Эффективный алгоритм поиска мостов был представлен в работе [13]. Он работает в синхронизированной сети, в модели с подписанными сообщениями и априорной плотной нумерацией узлов. В целом идея протокола о непосредственном поиске мостов в данной работе не отличается от идей из [13], но используются разные модели. Явный контроль посылаемых сообщений (отказ от подписей там, где это не нужно) позволяет улучшить оценки.

Глава 1. Определения

В этом разделе мы введём определения сети и протокола в ней - базовых понятий, с которыми будем работать, а также установим ряд их свойств.

Говоря неформально, сеть - это набор узлов и связей между ними, а протокол - алгоритм, в соответствии с которым эти узлы обмениваются сообщениями. Но есть множество различных нюансов, которые требуется учесть для строгой работы с понятиями. Именно поэтому местами определения кажутся громоздкими. Если же говорить кратко, то вот основные отличительные черты используемой в работе модели:

• Синхронизированное время: сообщения по всем связям передаются одновременно и мгновенно.

• Ограниченная пропускная способность каналов: за один сеанс передачи информации передаётся не более константного объёма информации. Стоит заметить, что это усиление модели относительно «тяжёлых сообщений», так как позволяет строить более адаптивные протоколы, и, таким образом, раньше (в смысле объёма полученной информации) менять своё поведение с учётом полученной информации.

• Вычислительная сила узлов не ограничивается. Нас интересуют прежде всего проблемы, связанные с обменом информацией, а не сложностью действий в узлах.

• Однородность протоколов: мы требуем, чтобы узлы исполняли один и тот же протокол, и мы хотим, чтобы он работал во всех ситуациях выделенного класса. То есть нам не интересны протоколы, которые правильно отработают в одной конкретной сети с одним конкретным начальным состоянием узлов. Мы стремимся строить как можно более универсальные протоколы.

Начнём вводить формальные определения с понятия сети, её нам удобно определить через индексную функцию.

Определение. Сетью С = (V, deg, Е) мы будем называть кортеж из трёх элементов, где

• первый элемент - множество вершин6 V;

• второй элемент - функция степени вершин йед:У ^ М;

• третий элемент - индексная функция Е: V X М ^ V X М, порождающая связи в сети. Причём индексная функция должна удовлетворять следующим условиям:

• Е(у, к) определено только для к из отрезка [0, deg(v)];

• Е(Е(р,к)) = (р,к); (связи двусторонние)

• Е(у,к) Ф (у,й), Уй. (отсутствие петель)

В данном определении мы не запретили явно кратные рёбра. Но в рассматриваемых нами задачах и протоколах они не оказывают никакого влияния. Для упрощения изложения будем далее предполагать, что сети связны и не имеют кратных рёбер.

Так же определим вспомогательные функции рЕ(у,к),гЕ(у,к), которые задаются равенством Е(рЕ(р,к),гЕ(р,к)) = (р,к). Эти функции позволяют найти «парное» к (р,к) полу-ребро.

Говоря неформально, все рёбра в графе имеют на каждом своём конце номер - локальный номер связи среди всех связей этой вершины. Функция Е позволяет нам по вершине и локальному номеру связи этой вершины получить вершину-сосед и локальный номер этой же связи в списке смежных с этим соседом. В отличие от обычных графов, задаваемых матрицей смежности:

1. связи, смежные с вершиной, имеют внешний порядок (он не индуцирован, например, порядком на самих вершинах);

2. при наличии кратных рёбер между парой вершин концы этих связей образуют некоторое нетривиальное паросочетание.

Данные свойства довольны естественны для сетей. Второе свойство формализует то, что если между двумя узлами установлено несколько соединений, то сообщения, отправленные че-

6 В работе термины «вершина» и «узел» можно воспринимать как синонимы. Конечно, термин «узел» более применим при рассмотрении вычислительных способностей и действиях в рамках протокола, а термин «вершина» при рассуждении о положении в сети. Но в работе чёткого разделения между ними не делается.

рез одно из них, можно получить только в соответствующем соединении на другой стороне «провода». Первое же свойство говорит о том, что узел может различать смежные с ним связи между собой, а значит и определить на них некоторый порядок, но такие порядки в разных узлах никак не обязаны быть согласованы между собой.

Там, где это не будет создавать неоднозначностей, мы будем применять стандартное обозначение Е(С) для множества всех связей графа.

Далее мы поэтапно будем двигаться к определению протокола и правилам обновления состояния узлов при работе протокола в сети с данным начальным состоянием. Мы стремимся дать такое определение, в котором явно определена информация, доступная узлу, и которую он может использовать для вычислений. Чтобы связать информацию в узле с топологией сети, мы введём понятие конфигурации - пары из сети и начальных состояний узлов.

Определение. Инициализирующей функцией узлов мы будем называть произвольную функцию вида ^ 2м.

Фактически, мы не накладываем никаких ограничений на /, разрешая использовать любую счётную структуру. В большинстве рассматриваемых нами примеров состояния будут конечными, счётные состояния будут полезны при определении вероятностных протоколов (в состояние каждого узла можно положить бесконечную битовую строку, а потом усреднять по мере на этих строках, см раздел 4.3).

Конфигурацией называется четвёрка (У,йед,Е,1) = (С,/), задающая и топологию сети, и начальное состояние узлов.

Семейством конфигураций с лидером называется множество конфигураций (С,/), где С = (У,йед,Е) пробегает все конечные связные сети (и, как было сказано выше, без петель и кратных рёбер), а индексная функция 1:У ^ {0,1} равна единице ровно на одной вершине из V.

Это достаточно важное семейство, так как в нём решена одна из проблем распределённых вычислений - разрушена симметрия: в сети существует управляющий и координирующий центр, который может принять окончательное решение. Например, можно строить протоколы

вида «передать всю информацию лидеру, а затем распространить ответ», хотя сделать даже это нетривиально, так как требуется, например, занумеровать узлы. И, конечно, данные решения не обязаны быть оптимальными по времени или трафику. Но существование хоть какого-то решения тоже важно.

Более того, если сеть не допускает выбора лидера (анонимные сети), то возможны ситуации, когда сеть не может решить задачу (см. приложение Б).

В главах номер 2 и 4 рассматривается вопрос о сведении более слабых конфигураций к сетям с лидером. А в разделе номер 3 рассматриваются задачи и протоколы в сетях с лидером.

Пусть фиксирован алфавит 1 - множество символов, которые можно передавать по связям. Для удобства можно считать, что мощность алфавита хотя бы 3, и он содержит выделенный элемент Л Е 1, который мы будем называть «пустым сообщением». При описании протоколов, если не указано иного, по связи будет передаваться А.

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

Определение. Протоколом будем называть любую функцию 5 аргументов вида

п(йЛ,5,ик) Е 1, где й,г,к Е МД < й.э Е 1 Е 2М.

Другими словами, протокол п - это функция, которая по степени вершины й, её начальному состоянию /, предыдущей истории общения з, моменту времени ^ определяет, какой символ послать по связи узла с номером к.

Из этого определения следует два важных свойства модели сети, о которых упоминалось ранее.

Во-первых, в сети синхронизированное время: можно разбить всё вычисление на чередующиеся стадии обработки состояния и посылки сообщений. То есть узлы на очередной стадии вычисления смотрят на всю доступную им информацию (а это только начальное состояние и полученные ранее сообщения) и принимают решение о том, какие сообщения отправить по каждой из связей на следующей стадии отправки сообщений.

Во-вторых, вычислительная сила узлов никак не ограничивается: требуется лишь детерминированность. Стоит заметить, что во всех рассматриваемых нами протоколах вычисления будут простыми - некоторые полиномиальные по длине истории алгоритмы.

Продолжим с определениями, перейдя к эволюции состояний узлов. Вводимые определения немного громоздки, но по сути они просты и лишь формализуют сделанные выше замечания.

Определение. Функция состояния Н сети в - это такая функция двух аргументов, что

н(г,р) еи*^^ и н(г,р) = (Н(г-1,р), н'(г,р)).

При этом Н(1,у) мы ассоциируем с множеством сообщений, полученных вершиной V к моменту времени t. Второе условие определения формализует то, что Н(1,у) должна удовлетворять естественному требованию согласованности: Н(1, р) получается из Н^ — 1, р) путём добавления ещё deg(v) символов в историю; через Н'(Ь,р) Е мы обозначили множество входящих сообщений V на шаге t.

Через Н'(1,у,к) обозначим к-й символ строки Н'(1,у), то есть символ, полученный узлом V по связи к.

Теперь мы наконец можем задать правило, по которому протокол п рекурсивно определяет функцию состояния Нп по конфигурации (V, йед, Е, I):

Ре(р, к), ге(р, к)) = ,1 — 1,нп(р,г — 1),1(р), к). (1)

Заметим, что определение корректно, так как пары (ре(^,к),ге(у,к)) составляют паросо-четание с (у,к), то есть если (у,к) пробегает все допустимые значения, то и (ре(у, к),ге(р, к))

пробегает все допустимые значения, а значит Н^ определено для всех (v,k). Взяв в качестве базы Hn(0,v) = 0 получаем, что Нп полностью определено.

Перейдём к определению понятия остановки протокола - нам хочется рассматривать протоколы, которые работают конечное время. Есть несколько вариантов определения: сильно-корректные, корректные и слабо-корректные протоколы. Приведём их, снабдив короткими комментариями.

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

Определение. Протокол п называется сильно-корректным в семействе конфигураций {(G,I)}, если найдётся функция end: (d,i,s,t) ^ х Е {0,1}, что для любой конфигурации (G,I) из рассматриваемого семейства найдётся такой момент времени t, что выполнено

1. Vv Е V end(deg(v) , I(v), Hn(v,t'),t') = [t' > t]; здесь [...] - индикаторная функция;

2. все узлы находятся в завершающем состоянии, состояние s = Hn(v,t) завершающее в протоколе п, то есть выполнено

n(deg(v),t',ss',I(v),k) = XVt' > t.Vk.Vs' Е zdeg(v)(t'-t).

Последнее условие формализует требование «при любых будущих входящих сообщениях узел не будет вступать в коммуникацию, то есть передавать что-либо, кроме пустых сообщений».

Удобно называть минимальное t, для которого выполняется условие 1, временем работы протокола п в конфигурации (G,I).

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

Корректные протоколы отличаются от сильно-корректных тем, что узлы могут переходить в завершающее состояние не обязательно одновременно. Сформулированная и доказанная ниже теорема 1.1 показывает, что корректные протоколы сводимы к сильно-корректным в сетях с лидером. Это позволит нам упростить описание протоколов.

Важным свойством завершающего состояния является то, что узел «знает», что он в завершающем состоянии, и никакие сообщения от соседей из этого состояния узел не выведут. Если ослабить такое свойство и ввести ждущее состояние - если все входящие сообщения были А, то и все исходящие сообщения будут А - то получится определение слабо-корректного протокола: протокол, при выполнении которого все узлы в некоторый момент времени окажутся в ждущем состоянии.

Список литературы диссертационного исследования кандидат наук Хузиев Ильнур Масхудович, 2019 год

Список литературы.

[1] Peleg D., Rubinovich V. A near-tight lower bound on the time complexity // SIAM J. on Computing, Т. 30, 2000, c 1427-1442.

[2] Dinitz Y., Moran Sh., Rajsbaum S. Bit complexity of breaking and achieving // Journal of the ACM Т. 55 №1 , С. 1-28 ,2008

[3] Itai A., Rodeh M., Symmetry breaking in distributed networks // Information and Computation, т. 88, № 1, С. 60-87, 1990.

[4] Frederickson G. N., Lynch N. A. Electing a leader in a synchronous ring // Journal of the ACM, Т. 34, С. 98-115, 1987.

[5] Burns J.E. A formal model for message passing systems // Tech. Rep. Indiana Univ, TR-91, 1980.

[6] Lynch N.A. Distributed algorithms. // San Francisco, CA, USA:: Morgan, 1996.

[7] Perlman R. An algorithm for distributed computation of a spanning tree in an extended LAN // ACM SIGCOMM Computer Communication Review, Т. 15, № 4, С. 44-53, 1985.

[8] Wattenhofer R. Principles of distributed computing // URL: http://dcg.ethz.ch/lectures/podc_allstars/lecture/podc.pdf, 2014.

[9] Вялый М.Н., Хузиев И.М. Распределённая коммуникационная сложность построения остовного дерева // Пробл. передачи информ., Т. 51, № 1, С. 54-71, 2015.

[10] Вялый М. Н., Хузиев И. М. Быстрые протоколы выбора лидера и построения остовного дерева в распределенной сети // Пробл. передачи информ., Т 53 № 2, С. 91-111, 2017.

[11] Хузиев И.М. Быстрая нумерация узлов в синхронной сети с сохранением структуры дерева // Дискретные модели в теории управляющих систем: X Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г.: Труды /М.: МАКС Пресс, 2018. - 296 с. ISBN 978-5-317-05834-0.

[12] Успенский В.А., Верещагин Н.К., Шень А. Колмогоровская сложность и алгоритмическая случайность // МЦНМО , 2010.

[13] Pritchard D. An Optimal Distributed Edge-Biconnectivity Algorithm // URL: https://arxiv. org/abs/cs/0602013.

[14] И. М. Хузиев, "О поиске антиподальных вершин в симметричном графе Кэли группы булева куба", Дискретн. анализ и исслед. опер., 22:1 (2015), 86-99; J. Appl. Industr. Math., 9:2 (2015), 206-214