Изменения

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

TODO* [[Диффундирующие вычисления]]* [[Алгоритм Дейкстры и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.]]

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

*[[Total orderОбщий порядок сообщений]]

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

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

'''Задача двух ===26 билет. Синхронные системы. Проблема византийских генералов''' — мысленный эксперимент. Невозможность решения при N = 3, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (f = 1===* [[Асинхронные и синхронные распределённые системы]]* [[Проблема византийских генералов]]* [[https://ru.wikipediaНевозможность византийского консенсуса]] при N=3, f=1.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B4%D0%B2%D1%83%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2 Википедия])

Два процесса === 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===* [[Иерархия ошибок в случае ненадежного канала не могут достичь распределённых системах]]* [[консенсус|консенсусаАсинхронные и синхронные распределённые системы]].* [[Консенсус в распределённой системе]]Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least (presumably the receiver) would decide not to attack. From the viewpoint of the sender of that last message, however, the sequence of messages sent and delivered is exactly the same as it would have been, had that message been delivered.* [[Алгоритм Бен-Ора]]

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

===26 30 билет. Синхронные системы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 консенсус невозможен. Данный вопрос достаточно хорошо описан в английской версии. === 27 35 билет. Недетерминированные Самостабилизирующиеся алгоритмы консенсуса. Алгоритм Бен-ОраИдея. Алгоритмы взаимного исключения и поиска остовного дерева ====== 28 билет. Paxos. Алгоритм, его свойства.====== 29 билет. Paxos. Общие принципы. Основные модификации.====== 30 билет. Транзакции в распределенных системах. 2 Phase Locking====== 31 билет. Транзакции * [[Иерархия ошибок в распределенных распределённых системах. 2 Phase Commit.===]]=== 32 билет. СAP теорема (концепции, подходы, без доказательства)====== 33 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===* [[Самостабилизирующиеся алгоритмы]]