Изменения

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

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

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

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

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

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

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

===713-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы=== *[[Глобальные свойства системы]]*[[Слабый конъюнктивный предикат (WCP)]]*[[Централизованный алгоритм для WCP]]*[[Распределенный алгоритм для WCP]] ===815 билет. Диффундирующие вычисления. Останов. Алгоритм Дейксты Дейкстры и Шолтена===* [[Диффундирующие вычисления]]* [[Алгоритм Дейкстры и Шолтена]] ===916 билет. Локально-стабильные предикаты, согласованные интервалаинтервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки=== *[[Локально стабильный предикат]]*[[Согласованный интервал]]*[[Барьерная синхронизация (3 алгоритма)]]*[[Определение взаимной блокировки]] ===1017-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка======11. Упорядочивание * [[Иерархия порядков сообщений. Определения, иерархия порядков. ]]* [[Алгоритм для FIFO порядка]]* [[Алгоритм для причинно-согласованного порядка]]* [[Алгоритм для синхронного порядка===]] ===1220-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина======13. Выбор лидера. *[[Общий порядок сообщений]]*[[Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===Лампорта]]===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===*[[Алгоритм Скина]]

#===22 билет. Иерархия ошибок в распределенных системах. Отказ узла#Отказ связи#Неустойчивая связь / пропуск пакетов#Византийская ошибка в асинхронной системе - невозможность консенсуса (сломавшийся процесс может слать любой мусордоказательство Фишера-Линча-Патерсона)===

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

===1523 билет. Синхронные системыКонсенсус в распределенных системах. Алгоритм для Применение консенсуса в случае отказа заданного числа узлов: выбор лидера, terminating reliable broadcast===* [[Иерархия ошибок в распределённых системах]]* [[Асинхронные и синхронные распределённые системы]]* [[Консенсус в распределённой системе]]* [[Переформулировки консенсуса в распределённой системе]]

Пусть в системе имеется ''n'' узлов===24 билет.Пусть из них максимум ''f'' не работаютСинхронные системы.Тогда можно решить задачу Алгоритм для консенсуса:в случае отказа заданного числа узлов===

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

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

Два процесса === 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===* [[Иерархия ошибок в случае ненадежного канала не могут достичь распределённых системах]]* [[консенсус|консенсусаАсинхронные и синхронные распределённые системы]]* [[Консенсус в распределённой системе]]* [[Алгоритм Бен-Ора]].

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

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

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями=== 31 билет. Как прийти к консенсусу честным генералам?Транзакции в распределенных системах. 2 Phase Locking===* [[Транзакции в распределённых системах]]* [[2 Phase Locking]]

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

*Каждый рассылает каждому свое число;=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===*Каждый рассылает каждому собранные значения;*В полученных векторах каждый проводит голосование.[[CAP теорема]]

Можно доказать=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, напримерпримеры алгоритмов, что при ''n'' см. работу с семинара)== 3, ''f'' = 1 консенсус невозможен.* [[Gossip-протоколы]]* [[CRDT]]

===1835 билет. Синхронные системыСамостабилизирующиеся алгоритмы. Проблема византийских генераловИдея. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1Алгоритмы взаимного исключения и поиска остовного дерева ===* [[Иерархия ошибок в распределённых системах]]* [[Самостабилизирующиеся алгоритмы]]

Данный вопрос достаточно хорошо описан в <ref>http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B2%D0%B8%D0%B7%D0%B0%D0%BD%D1%82%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2==Ссылки==<references/ref>.