292
правки
Изменения
→20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина
===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) ===19 билет. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка=== Алгоритм для синхронного порядка основан на иерархии процессов.Упорядочим процессы по номеру, назовем сообщение ''большим'', если номер отправителя больше номера получателя, и ''малым'' иначе.Процесс может быть в ''активном'' или ''пассивном состоянии''. Изначально все активны.Процесс может отправить большое сообщение, только если он активен. После отправки он становится пассивным и не может ни отправлять, ни принимать сообщения, пока не получит от получателя ack.
===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 выбором варианта, который больше встречается). Если же все процессы равноправные, то в 0 раунде рассылки все считают себя "генералами", а потом делаем консенсус на исходных значениях каждого. Выбор варианта в конечном итоге даст правильный вариант именно потому, что N > 3f.решения проблемы
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
* [[Асинхронные и синхронные распределённые системы]]
* [[Проблема византийских генералов]]
* [[Невозможность византийского консенсуса]] при N=3, f=1.
=== 28 билет. Paxos. Алгоритм, его свойства.===
=== 29 билет. Paxos. Общие принципы. Основные модификации.===
=== 30 билет. Транзакции в распределенных системахRaft. Алгоритм, его свойства. 2 Phase Locking====== 31 билет. Транзакции в распределенных системах. 2 Phase Commit.Locking====== 32 билет. СAP теорема (концепции, подходы, без доказательства)===* [[Транзакции в распределённых системах]]=== 33 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===CRDT (Conflict-Free Replicated Data Type) — объект, который можно реплицировать на много узлов и обновлять параллельно без координации между узлами. '''Репликация на основе состояния''' Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д.. Достаточные условия согласованности: 1. Множество возможных состояний образует полурешетку, т.е. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;* [[2 Phase Locking]]
=== 32 билет. Транзакции в распределенных системах. 2Phase Commit. Обновления возрастают.===* [[Транзакции в распределённых системах]]* [[2 Phase Commit]]
==Ссылки==
<references/>