Изменения

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

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

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

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

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

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

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

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

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

===1627 билет. Синхронные системыНедетерминированные алгоритмы консенсуса. Проблема двух генераловАлгоритм Бен-Ора. Невозможность получения общей информации===* [[Иерархия ошибок в распределённых системах]]'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (* [[https://ru.wikipedia.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-ого все испортилось. ===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы=== '''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)Ора]]

Проблема византийских генералов формулируется так: имеется ''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 теорема]]

Данный вопрос достаточно хорошо описан в английской версии=== 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 (концепции, примеры алгоритмов, см. работу с семинара)===* [[Самостабилизирующиеся алгоритмы]]