Изменения

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

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

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

===1220-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===*[[Total orderОбщий порядок сообщений]]

===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера=== '''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>. Пусть процессы находятся в кольце. Посылаем свой номер налево по кольцу. При получении номера справа посылаем налево максимум из своего номера и полученного справа.Если полученный справа номер является нашим номером, то заканчиваем работу. '''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref> <ref>http://web.cs.gc.cuny.edu/~vmitsou/presentation.pdf слайды 16-18</ref>. ===1422 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательствоФишера-Линча-Патерсона)=== #Отказ узла#Отказ связи#Неустойчивая связь / пропуск пакетов#Византийская ошибка (сломавшийся процесс может слать любой мусор) Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа. Также решение - уйти от требования детерминированности алгоритма. ===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов=== Пусть в системе имеется ''n'' узлов.Пусть из них максимум ''f'' не работают.Тогда можно решить задачу консенсуса: *Каждый узел посылает каждому свое число;*Процессы запоминают пришедшие числа;*Новые для себя числа процессы рассылают дальше;*Каждый процесс выбирает минимально известное ему число.

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

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

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи===24 билет. ([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===25 билет. 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Алгоритм для N >= 4, had that message been deliveredf = 1.Объяснить идею обобщения для f > 1===* [[Асинхронные и синхронные распределённые системы]]* [[Проблема византийских генералов]]* [[Алгоритм Лампорта-Шостака-Пиза]] для решения проблемы

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

===1727 билет. Синхронные системыНедетерминированные алгоритмы консенсуса. Проблема византийских генераловАлгоритм Бен-Ора. Невозможность решения при 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 теорема]]

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

Данный вопрос достаточно хорошо описан === 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева ===* [[Иерархия ошибок в английской версии.распределённых системах]]* [[Самостабилизирующиеся алгоритмы]]