Изменения

===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. Выбор лидера. *[[Общий порядок сообщений]]*[[Алгоритм Лампорта]]*[[Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===Скина]] ===1422 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательствоФишера-Линча-Патерсона)===

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

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

===1524 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

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

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

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

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи=== 27 билет. (Википедия)Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===* [[Иерархия ошибок в распределённых системах]]* [[Асинхронные и синхронные распределённые системы]]* [[Консенсус в распределённой системе]]* [[Алгоритм Бен-Ора]]

Два процесса === 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===* [[Консенсус в случае ненадежного канала не могут достичь распределённой системе]]* [[консенсус|консенсусаReplicated State Machine]]* [[Paxos]].

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

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем === 31 билет. Транзакции в случае, когда коммуникации считаются надёжными, а процессоры — нетраспределенных системах. (Вики)2 Phase Locking===* [[Транзакции в распределённых системах]]* [[2 Phase Locking]]

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

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

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

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен= 35 билет. Самостабилизирующиеся алгоритмы. Идея.Алгоритмы взаимного исключения и поиска остовного дерева ===* [[Иерархия ошибок в распределённых системах]]* [[Самостабилизирующиеся алгоритмы]]

==Ссылки=18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f <references/> 1===