Изменения

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

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

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

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

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

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

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

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

Алгоритм Чанди-Робертса (Chang and Roberts) выбора лидера <ref>http://en===15 билет.wikipediaДиффундирующие вычисления.org/wiki/Chang_and_Roberts_algorithm</ref>Останов.Алгоритм Дейкстры и Шолтена===* [[Диффундирующие вычисления]]* [[Алгоритм Дейкстры и Шолтена]]

Пусть процессы находятся в кольце===16 билет. Посылаем свой номер налево по кольцу. При получении номера справа посылаем налево максимум из своего номера и полученного справа.Если полученный справа номер является нашим номеромЛокально-стабильные предикаты, согласованные интервалы, то заканчиваем работубарьерная синхронизация (3 алгоритма).Применение для определения взаимной блокировки===

===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса *[[Локально стабильный предикат]]*[[Согласованный интервал]]*[[Барьерная синхронизация (доказательство3 алгоритма)===]]*[[Определение взаимной блокировки]]

Отказ одного узла в распределенной системе ведет к невозможности консенсуса===20-21 билеты. Решением является уход от асинхронизации, накладывание ограничений на время ответаОбщий порядок (total order).Алгоритмы Лампорта и Скина===*[[Общий порядок сообщений]]*[[Алгоритм Лампорта]]*[[Алгоритм Скина]]

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

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

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

===1624 билет. Синхронные системы. Проблема двух генералов. Невозможность получения общей информацииАлгоритм для консенсуса в случае отказа заданного числа узлов===

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

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

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

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

Известно, что при ''n'' > 3''f'' задача решаема=== 30 билет. Raft. Алгоритм, а иначе нетего свойства.===* [[Консенсус в распределённой системе]]* [[Replicated State Machine]]* [[Raft]]

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

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

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

Данный вопрос достаточно хорошо описан в <ref>http://ru=== 34 билет.wikipediaGossip.org/wiki/Задача_византийских_генералов</ref>СRDT и дельта-CRDT (концепции, примеры алгоритмов, см.работу с семинара)===* [[Gossip-протоколы]]* [[CRDT]]