Теормин

Теоретический минимум по курсу

«Распределённые алгоритмы и системы» (весна 2016)

лектор – Захаров Владимир Анатольевич

Составитель: avasite

Оглавление

1. Распределенные системы и их характерные особенности. Архитектура распределенных систем. Алгоритмические проблемы организации вычислений распределенных систем. Особенности распределенных алгоритмов. 2

2. Математическая модель. Системы переходов. Системы с синхронным и асинхронным обменом сообщениями. Свойство справедливости выполнений системы. Зависимые и независимые события. Причинно-следственный порядок событий. Эквивалентность выполнений. Вычисления. Логические часы. 3

3. Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Симметричный протокол раздвижного окна. Устройство протокола раздвижного окна. Принципы обоснования корректности протоколов Обоснование корректности протокола раздвижного окна. Модификации протокола. 5

4. Коммуникационный протокол с таймерами. Допущения о времени. Таймеры. Устройство протокола с таймерами. Обоснование корректности протокола с таймерами. Модификации протокола. 6

5. Задача маршрутизации. Маршрутизация на основе узлов-адресатов. Задача построения кратчайших путей для всех пар вершин. Алгоритм Флойда-Уоршалла. Алгоритм Туэга. Алгоритм Мерлина-Сигалла. Алгоритм Чанди-Мисры. 7

6. Алгоритм маршрутизации Netchange. Описание алгоритма. Инварианты алгоритма Netchange. Корректность алгоритма Netchange. Сходимость алгоритма Netchange. Особенности реализации алгоритма. Другие виды маршрутизации: интервальная, префиксная, иерархическая. 9

7. Волновые алгоритмы: определения, основные свойства, область применения. Древесный алгоритм. Алгоритм эха. 10

8. Волновые алгоритмы. Фазовый алгоритм. Алгоритм Финна. Распределенные алгоритмы обхода: основные свойства. Алгоритм обхода Тарри. Распределенный обход в глубину. Алгоритмы Авербаха и Сидона. 12

9. Задача избрания лидера. Основные определения и допущения. Волновые алгоритмы избрания лидера. Выборы лидера на дереве. Выборы в кольцах. Алгоритм Ле-Ланна. Алгоритм Ченя - Робертса. Алгоритм Петерсона/Долева-Клейва-Роде. Эффект угасания. 14

10. Задача избрания лидера. Нижние оценки сложности. Оптимальные выборы. Алгоритм Галладжера-Хамблета-Спиры (GHS). Глобальное описание алгоритма GHS. Подробное описание алгоритма GHS. Алгоритм Корача-Каттена-Морана. 15

11. Задача обнаружения завершения вычислений. Алгоритм Дейкстры-Шолтена. Алгоритм Шави-Франчеза. Алгоритм Сафры. Алгоритм возвращения кредитов. 17

12. Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта Алгоритм Лаи-Янга. Применение алгоритмов сохранения моментального состояния. 20

1. Распределенные системы и их характерные особенности. Архитектура распределенных систем. Алгоритмические проблемы организации вычислений распределенных систем. Особенности распределенных алгоритмов.

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

Взаимодействующие компьютеры, процессы или программы называют узлами распределенной системы.

Механизм организации связи между узлами называют коммуникационной подсистемой.

Распределенные алгоритмы - это алгоритмы, определяющие функционирование распределенных систем.

Примеры распределенных систем:

• глобальные коммуникационные вычислительные сети

• локальные вычислительные сети

• многопроцессорные компьютеры

• системы взаимодействующих процессов.

Зачем нужны распределенные системы?

1. Обмен информацией

2. Совместное использование ресурсов

3. Повышение надежности за счет дублирования

4. Повышение производительности за счет параллельного выполнения

5. Упрощение проектирования за счет специализации

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

Основные отличия между глобальными и локальными сетями:

1. Параметры надежности.

2. Время связи.

3. Однородность аппаратуры и программного обеспечения.

4. Взаимное доверие.

Алгоритмические проблемы для глобальных сетей:

1. Обеспечение надежного обмена данными по двухточечной линии связи.

2. Выбор каналов связи - задача маршрутизации пакетов.

3. Устранение перегрузки в сети.

4. Предотвращение блокировки (тупиков) - задача неблокируемой коммутации.

5. Обеспечение безопасности.

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

Алгоритмические проблемы для локальных сетей:

1. Широковещательное распространение и синхронизация.

2. Избрание лидера.

3. Обнаружение завершения.

4. Обеспечение корректного использования ресурсов.

5. Обнаружение и устранение тупиков.

6. Распределенное обслуживание файлов.

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

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

А если он предназначен для повышения надежности вычислений, то его называют вычислительной системой с дублированием.

Алгоритмические проблемы для многопроцессорных компьютеров:

1. Реализация системы передачи сообщений - маршрутизация, устранение перегрузки и блокировок.

2. Реализация виртуальной разделяемой памяти.

3. Уравновешивание нагрузки.

4. Устойчивость к необнаруживаемым сбоям.

Алгоритмические проблемы для систем взаимодействующих процессов:

1. Атомарность операций записи и считывания.

2. Синхронизация процессов.

3. Сборка мусора.

4. Обмен сообщениями.

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

Архитектурой сети называется совокупность всех модулей (уровней), вместе с определениями соответствующих интерфейсов и протоколов.

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

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

Коммуникация осуществляется посредством обмена сообщениями (обеспечивает как коммуникацию, так и синхронизацию) и/или при помощи совместно используемой памяти (обеспечивает только коммуникацию)

Недетерминизм выражается при помощи охраняемых команд.

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

Особенности распределенных алгоритмов:

1. Отсутствие сведений о глобальном состоянии.

2. Отсутствие глобальной шкалы времени.

3. Недетерминизм.

1. Математическая модель. Системы переходов. Системы с синхронным и асинхронным обменом сообщениями. Свойство справедливости выполнений системы. Зависимые и независимые события. Причинно-следственный порядок событий. Эквивалентность выполнений. Вычисления. Логические часы.

От модели требуется быть: точной, общей, компактной.

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

Система переходов – это тройка <конфигурация, отношение переходов, начальные конфигурации>

Выполнение системы переходов – максимальная последовательность, удовлетворяющая системе переходов.

Заключительная конфигурация (если из неё нету перехода).

Максимальное выполнение – выполнение, которое либо бесконечное, либо заканчивается заключительной конфигурацией.

Распределенная система состоит из совокупности процессов и коммуникационной подсистемы.

События бывают 3-х типов: внутренние, отправления и приёма.

Соглашение:

Термины переход и конфигурация будут использоваться применительно ко всей распределенной системе в целом.

Термины событие и состояние, обозначающие равносильные понятия, будут использоваться, если речь идет о процессах системы.

Локальный алгоритм процесса – это пятёрка <состояния, начальные состояния, внутренние действия, отправление и приём сообщения>

Распределённый алгоритм семейства процессов – совокупность локальных алгоритмов, каждый из которых в точности соответствует одному процессу.

Система переходов асинхронно взаимосвязанных процессов –

Система переходов синхронно связанных процессов –

Соглашение:

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

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

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

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

Пространственно-временная диаграмма.

Теорема 1.

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

Отношение причинно-следственного порядка – (задано выполнение E) – это наименьшее отношение, удовлетворяющее следующим условиям:

1. Если e и f – 2 разных события одного процесса, и е происходит прежде события f, то e <- f.

2. Если s – это событие отправления сообщения, а r – это события принятия этого сообщения, то s<-r.

3. «<-» - обладает свойством транзитивности

«<=» - отношение частичного порядка, которое определяется формулой (a<-b or a=b)

События, для которых не выполняются a<=b и b<=a – называются параллельными.

Теорема 2.

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

Эквивалентные выполнения (~) – выполнения, в которых одно и тоже множество событий, в котором задан один и тот же причинно-следственный порядок событий.

Вычислением распределенного алгоритма называется класс эквивалентности выполнений алгоритма по отношению эквивалентности ~.

Часы – всякая функция, которая отображает множество событий в некоторое упорядоченное множество так, что при этом сохраняется отношение причинно-следственного порядка.

Логические часы Лэмпорта – по сути они тикают на +1 на каждом шаге в каждом процессе, но когда приходит сообщение от другого процесса, то там также указан момент времени, когда сообщение было послано, и если этот тик больше локального тика, то локальный тик увеличивается до него.

Определение формулируется через максимальную длину частично упорядоченной последовательности событий всех различных выполнений.

Асинхронные системы – менее безопасны, но более живучи.

Свойства каналов связи: надёжность, свойство очерёдности, пропускная способность каналов

Осведомлённость процессов: топологическая информация, отличительные признаки процессов, отличительные признаки соседей.

Сложность распределённых алгоритмов: по числу обменов сообщениями, битовая сложность, сложность по времени.

1. Коммуникационные протоколы. Ошибки, возникающие при передаче сообщений. Симметричный протокол раздвижного окна. Устройство протокола раздвижного окна. Принципы обоснования корректности протоколов Обоснование корректности протокола раздвижного окна. Модификации протокола.

(лекция специфична, подробнее см. слайды)

Определение 3.1

Пусть задана система переходов S = (C, ->, I) и рассматриваются некоторые свойства конфигураций P и Q.

Запись P(y), где y — конфигурация, будет обозначать логическое выражение (формулу), принимающее истинное значение в том случае, если утверждение P справедливо для конфигурации y, и ложное значение в противном случае. Запись {P} -> {Q} будет использоваться для обозначения того, что для каждого перехода y -> z в системе S истинность P(y) влечет истинность Q(z).

Утверждение P называется инвариантом системы S, если

1. P (y) истинно для каждой начальной кон фигурации y ∈ I и

2. {P} ^ {P}

Теорема 3.1

Если утверждение P является инвариантом системы переходов S, то доя любого выполнения E системы S утверждение P будет истинно в каждой конфигурации этого выполнения.

Теорема 3.2.

Если Q является инвариантом системы переходов S, и для каждой конфигурации y ∈ C выполняется Q(y) => P(y), то для любого выполнения системы S утверждение P будет истинно в каждой конфигурации выполнения.

Определение 3.2.

Пусть задан признак правильного завершения выполнений Р. Система S правильно завершает выполнения (или, иными словами, свободна от блокировки), если предикат (term => Р) всегда является истинным для системы S.

Определение 3.3.