Изменения

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

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

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

TODO? (CHECK) *[[Total orderОбщий порядок сообщений]]

#Отказ одного или нескольких узлов (crash)* [[Иерархия ошибок в распределённых системах]]#Отказ одного или нескольких каналов (link failure)#Ненадежная доставка сообщений (omission)#Византийская ошибка (byzantine failure) (сломавшийся процесс может слать любой мусор)* [[Асинхронные и синхронные распределённые системы]]* [[Консенсус в распределённой системе]]* [[Теорема FLP (ФишерФишера-ЛинчЛинча-ПатерсонПатерсона (FLP):Для асинхронной системы N потоков с хотя бы одним сбойным потоком нельзя построить решение задачи консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа. Также решение - уйти от требования детерминированности алгоритма. Инфо: http://bailonga.es/tpmtp/lecture09.pdf + презентация Р.Елизарова]]

TODO* [[Иерархия ошибок в распределённых системах]] Результат FLP о невозможности консенсуса верен даже если, процессу разрешено делать операцию «атомарной передачи» сообщения сразу несколько процессам, ибо нет гарантии что все процессы обработают его. Если есть гарантия получения сообщения всеми процессами (или ни одним), то такая операция называется Terminating Reliable Broadcast (TRB). Имея TRB можно тривиально на его основе написать алгоритм консенсуса. Применение консенсуса:1) Выбор лидера* [[Асинхронные и синхронные распределённые системы]]* Каждый процесс предлагает себя. [[Консенсус определяет лидера для последующего распределенного алгоритма2) Terminating Reliable Broadcast* Надо прийти к консенсусу о том, надо ли обрабатыватьполученное сообщениев распределённой системе]]* Таким образом, задача TRB эквивалентна задаче [[Переформулировки консенсусав распределённой системе]]

Пусть * [[Иерархия ошибок в системе имеется ''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 Википедия])

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]]. 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. Для недетерминнированного - аналогично. Посмотрим на "успешную" последовательность.И отменим успешность последнего сообщения. Для 1-ого все ок, для 2-ого все испортилось. ===26 27 билет. Синхронные системыНедетерминированные алгоритмы консенсуса. Проблема византийских генераловАлгоритм Бен-Ора. Невозможность решения при 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 теорема]]

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

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