292
правки
Изменения
→30 билет. Raft. Алгоритм, его свойства.
[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
*[[Базовые определения и формализм]]
*[[Алгоритмы взаимного исключения]]
*[[Стек Трайбера]]
*[[Формализм распределённых систем]]
==6 семестр==
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]](билет весной 2019 года убран)
===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]
* Применение для определения дедлока. Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найден. Рассмотрим два среза: * когда взаимно блокирующие процессы прислали координатору свои графы;* когда они прислали ему notChanged.Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен. ===17-18 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка ===TODO Порядок сообщений:# асинхронный (нет порядка) # FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены в смысле одного потока)# причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком, а не в смысле одного потока, как в FIFO)# синхронный (можно выстроить ребра передачи сообщений без пересечений) Алгоритм FIFO основан на нумерации сообщений.<br>Псевдокод алгоритма для причинно-согласованного порядка. Вместе с сообщением отправляем матрицу M: M[i, j] — количество сообщений, отправленных процессом i процессу j. '''var''' M:array[l..N, 1..N] of integer initially 0; To send a message to <tex>P_j</tex>: M [i,j] := M[i,j] + 1; send M as part of the message; To receive a message with matrix W from Pj: '''enabled if''' W[j,i] = M [j,i] + 1 <tex>\land</tex> <tex> \forall k \neq j</tex> <tex>M[k, iОпределение взаимной блокировки] \geqslant W[k, i]</tex> M := max(M, W)
===17-19 билетбилеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка===* [[Иерархия порядков сообщений]]* [[Алгоритм для синхронного FIFO порядка основан на иерархии процессов.]]Упорядочим процессы по номеру, назовем сообщение ''большим'', если номер отправителя больше номера получателя, и ''малым'' иначе.* [[Алгоритм для причинно-согласованного порядка]]Процесс может быть в ''активном'' или ''пассивном состоянии''. Изначально все активны.Процесс может отправить большое сообщение, только если он активен. После отправки он становится пассивным и не может ни отправлять, ни принимать сообщения, пока не получит от получателя ack. Чтобы отправить сообщение большему процессу <tex>P_j</tex>, процесс <tex>P_i</tex> сначала посылает служебное сообщение, ''запрос''. В ответ <tex>P_j</tex> отправляет ''разрешение''; он может сделать это только в активном состоянии. Разрешив, он становится пассивным и остается в этом состоянии, пока не получает сообщение, которое разрешил.* [[Алгоритм для синхронного порядка]]
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
*[[Алгоритм Лампорта]]
*[[Алгоритм Скина]]
===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===
===23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast===
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
* [[Асинхронные и синхронные распределённые системы]]* [[Проблема византийских генералов - придти к нетривиальному консенсусу N процессам, если среди них есть f сбойных(могут вести себя как угодно/контролируются злоумышленниками).]]* [[Алгоритм Лампорта(и еще 2 человек):Считаем, что у процессов есть номера. Процесс 1 - "генерал" Шостака- рассылает всем предложение - 0 или 1. И после этого молчит(принимает своё предложение). При f=0 все остальные ("лейтенанты") просто принимают предложение. При f=1 все "лейтенанты" рассылают всем "лейтенантам" сообщение "генерал сказал X". Теперь у каждого процесса есть N-1 сообщение вида "A сказал, что генерал сказал X", включая своё(Я сказал, что генерал сказал X). Выбираем вариант, который встречается больше раз, или 0 если одинаково. Если сбойный процесс - генерал, то все остальные процессы получат одинаковое количество 0 и 1 в сообщениях и выберут одинаковый вариант. Если сбойный процесс - лейтенант, все остальные процессы получат больше верных сообщений, чем неверных и выберут вариант, посланный генералом. При f=2+ делаем всего f раундов рассылки сообщений между лейтенантами (при f=2 посылаются сообщения "B сказал, что A сказал, что генерал сказал X"), и f раундов выбора большинства внутри каждого процесса (т.е. Пиза]] для f=2 процесс имеет N-1 сообщение "B сказал, что А сказал ..." и решает, что именно сказал A выбором варианта, который больше встречается).решения проблемы
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
* [[Асинхронные и синхронные распределённые системы]]'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики) * [[Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам? Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.]]*Каждый рассылает каждому свое число;*Каждый рассылает каждому собранные значения;*В полученных векторах каждый проводит голосование. Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен. Доказательство от Елизарова: Пусть каждому процессу подаётся число 0 или 1 на вход(могут быть разными на разных процессах). Задача - прийти к нетривиальному консенсусу всем работающим процессам на одном значении, которое было дано на вход хотя бы одному работающему процессу. (Сильный консенсус) [[Файл:byzantine.png|frame|rightНевозможность византийского консенсуса]] Предположим обратное. Пусть существует алгоритм консенсуса. Тогда расставим 4 ноды с этим алгоритмом, подадим верхним на вход 0, и нижним = 1. Тогда если считать 2 верхних процесса рабочими, а 2 нижних - одним сбойным, верхние обязаны прийти к консенсусу на 0. Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних - одним сбойным - нижние приходят к консенсусу на 1. И если мы считаем рабочими 2 правых, а 2 левых - одним сбойным(ведущим себя как пара из верхнего рабочего и нижнего рабочего) - то верхний правый придет к консенсусу на 0 вместе с воображаемым верхним соседом, а нижний правый - к консенсусу на 1 с воображаемым нижним соседом. Fail. Поэтому такого алгоритма нет, и консенсус при N=3 и , f=1 невозможен.
=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
=== 32 билет. Транзакции в распределенных системах. 2Phase Commit. Обновления возрастают.===* [[Транзакции в распределённых системах]]* [[2 Phase Commit]]
==Ссылки==
<references/>