Изменения

===1Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===

===1-2билеты. Логические часы Лампорта и векторные часы, их свойства===

===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===

*[[Параллельное программирование: Матричные часы|Матричные часы]](билет весной 2019 года убран)

===45-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===

===58-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

===611-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителяи получателя===

===713-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Слабый конъюнктивный предикат(WCP)]]*[[Централизованный алгоритм для WCP]]*[[Распределенный алгоритм для WCP]]

===815 билет. Диффундирующие вычисления. Останов. Алгоритм Дейксты Дейкстры и Шолтена===* [[Диффундирующие вычисления]]* [[Алгоритм Дейкстры и Шолтена]]

Алгоритм Дейксты и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>. ===916 билет. Локально-стабильные предикаты, согласованные интервалаинтервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===

===1017-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка===Порядок * [[Иерархия порядков сообщений:]]# асинхронный# * [[Алгоритм для FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены)порядка]]# * [[Алгоритм для причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком)согласованного порядка]]# синхронный* [[Алгоритм для синхронного порядка]]

===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка======1220-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===*[[Total orderОбщий порядок сообщений]]

*[[Алгоритм СкринаСкина]] ===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера=== '''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>. Пусть процессы находятся в кольце. Посылаем свой номер налево по кольцу. При получении номера справа посылаем налево максимум из своего номера и полученного справа.Если полученный справа номер является нашим номером, то заканчиваем работу. '''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref> <ref>http://web.cs.gc.cuny.edu/~vmitsou/presentation.pdf слайды 16-18</ref>. ===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)=== #Отказ узла#Отказ связи#Неустойчивая связь / пропуск пакетов#Византийская ошибка (сломавшийся процесс может слать любой мусор) Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

===1522 билет. Синхронные системыИерархия ошибок в распределенных системах. Алгоритм для Отказ узла в асинхронной системе - невозможность консенсуса в случае отказа заданного числа узлов(доказательство Фишера-Линча-Патерсона)===

Пусть * [[Иерархия ошибок в распределённых системах]]* [[Асинхронные и синхронные распределённые системы]]* [[Консенсус в распределённой системе имеется ''n'' узлов.Пусть из них максимум ''f'' не работают.]]Тогда можно решить задачу консенсуса:* [[Теорема Фишера-Линча-Патерсона (FLP)]]

===23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast===*Каждый узел посылает каждому свое число;[[Иерархия ошибок в распределённых системах]]*Процессы запоминают пришедшие числа;[[Асинхронные и синхронные распределённые системы]]*Новые для себя числа процессы рассылают дальше;[[Консенсус в распределённой системе]]*Каждый процесс выбирает минимально известное ему число.[[Переформулировки консенсуса в распределённой системе]]

===16. Синхронные * [[Иерархия ошибок в распределённых системах]]* [[Асинхронные и синхронные распределённые системы. Проблема двух генералов. Невозможность получения общей информации===]]* [[Консенсус в распределённой системе]]* [[Консенсус в синхронных системах]]

'''Задача двух ===25 билет. Синхронные системы. Проблема византийских генералов''' — мысленный эксперимент. Алгоритм для N >= 4, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связиf = 1. (Википедия)Объяснить идею обобщения для f > 1===* [[Асинхронные и синхронные распределённые системы]]* [[Проблема византийских генералов]]* [[Алгоритм Лампорта-Шостака-Пиза]] для решения проблемы

Два процесса в случае ненадежного канала не могут достичь ===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===* [[консенсус|Асинхронные и синхронные распределённые системы]]* [[Проблема византийских генералов]]* [[Невозможность византийского консенсуса]]при N=3, f=1.

===1727 билет. Синхронные системыНедетерминированные алгоритмы консенсуса. Проблема византийских генераловАлгоритм Бен-Ора. Невозможность решения при N=3, f=1. Формулировка общей теоремы===* [[Иерархия ошибок в распределённых системах]]* [[Асинхронные и синхронные распределённые системы]]* [[Консенсус в распределённой системе]]* [[Алгоритм Бен-Ора]]

'''Задача византийских генералов''' — мысленный эксперимент=== 28-29 билеты. Paxos. Алгоритм, призванный проиллюстрировать проблему синхронизации состояния систем его свойства. Общие принципы. Основные модификации.===* [[Консенсус в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)распределённой системе]]* [[Replicated State Machine]]* [[Paxos]]

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями=== 30 билет. Как прийти к консенсусу честным генералам?Raft. Алгоритм, его свойства.===* [[Консенсус в распределённой системе]]* [[Replicated State Machine]]* [[Raft]]

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет=== 31 билет.Транзакции в распределенных системах. 2 Phase Locking===* [[Транзакции в распределённых системах]]* [[2 Phase Locking]]

*Каждый рассылает каждому свое число;=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===*Каждый рассылает каждому собранные значения;[[Транзакции в распределённых системах]]*В полученных векторах каждый проводит голосование.[[2 Phase Commit]]

Можно доказать=== 33 билет. СAP теорема (концепции, напримерподходы, что при ''n'' без доказательства)== 3, ''f'' = 1 консенсус невозможен.* [[CAP теорема]]

===1834 билет. Синхронные системыGossip. Проблема византийских генералов. Алгоритм для N >= 4СRDT и дельта-CRDT (концепции, примеры алгоритмов, f = 1см. Объяснить обобщение для f > 1работу с семинара)===* [[Gossip-протоколы]]* [[CRDT]]

Данный вопрос достаточно хорошо описан в <ref>http://ru=== 35 билет.wikipediaСамостабилизирующиеся алгоритмы.org/wiki/Задача_византийских_генералов</ref>Идея.Алгоритмы взаимного исключения и поиска остовного дерева ===* [[Иерархия ошибок в распределённых системах]]* [[Самостабилизирующиеся алгоритмы]]