1632
правки
Изменения
м
TODO
TODO? (CHECK)
TODO Результат FLP о невозможности консенсуса верен даже если, процессу разрешено делать операцию «атомарной передачи» сообщения сразу несколько процессам, ибо нет гарантии что все процессы обработают его. Если есть гарантия получения сообщения всеми процессами (или ни одним), то такая операция называется Terminating Reliable Broadcast (TRB). Имея TRB можно тривиально на его основе написать алгоритм консенсуса (процесс <tex>P_0</tex> рассылает всем свой бит, они соглашаются на этот бит, если получили сообщение, иначе на 0). Применение консенсуса: 1) Выбор лидера* [[Иерархия ошибок в распределённых системах]]* [[Асинхронные и синхронные распределённые системы]]* Каждый процесс предлагает себя. [[Консенсус определяет лидера для последующего распределенного алгоритма 2) Terminating Reliable Broadcast * Надо прийти к консенсусу о том, надо ли обрабатывать полученное сообщениев распределённой системе]]* Таким образом, задача TRB эквивалентна задаче [[Переформулировки консенсусав распределённой системе]]
Как известно из FLP, при всех требованиях консенсус невозможен. Уберем требование асинхронности (любое сообщение доходит за некоторое конечное время). Пусть в системе имеется ''n'' узлов, каждому задано начальное число.Пусть из них максимум ''f'' могут в любой момент упасть(crash).Тогда можно решить задачу консенсуса за ''f+1'' раундов: *Делаем [[Иерархия ошибок в каждом узле вектор из ''n'' значений (своё записываем, остальные пока неизвестны)распределённых системах]]*В каждом раунде каждый узел посылает каждому все свои числа (или только те, которые не посылал ранее - без разницы)[[Асинхронные и синхронные распределённые системы]]*Процессы записывают пришедшие числа [[Консенсус в свой векторраспределённой системе]]*После ''f+1'' - го раунда выбираем минимум из известных чисел. Почему это работает?Допустим, что процессы a и b выбрали разные минимумы. Значит, есть значение v, которое есть у одного из процессов и нет у другого(пусть есть у b). Но если у нас был раунд без сбоев, то все процессы узнают все имеющиеся [[Консенсус в данный момент числа - потому что все сообщения дошли. А сбоев было не больше f - противоречие.синхронных системах]]
=== 28 билет. Paxos. Алгоритм, его свойства.====== 29 билет. Paxos. Общие принципы. Основные модификации.====== 30 билет. Транзакции * [[Иерархия ошибок в распределенных распределённых системах. 2 Phase Locking===]]* [[Асинхронные и синхронные распределённые системы]]=== 31 билет. Транзакции * [[Консенсус в распределенных системах. 2 Phase Commit.===распределённой системе]]=== 32 билет. СAP теорема (концепции, подходы, без доказательства)====== 33 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===CRDT (Conflict* [[Алгоритм Бен-Free Replicated Data Type) — объект, который можно реплицировать на много узлов и обновлять параллельно без координации между узлами.Ора]]
'''Репликация на основе состояния'''=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===* [[Консенсус в распределённой системе]]* [[Replicated State Machine]]* [[Paxos]]
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике=== 30 билет. Raft. Та применяет функцию mergeАлгоритм, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д.свойства. ===* [[Консенсус в распределённой системе]]* [[Replicated State Machine]]* [[Raft]]
Достаточные условия согласованности:=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===* [[Транзакции в распределённых системах]]* [[2 Phase Locking]]
1=== 32 билет. Множество возможных состояний образует полурешетку, тТранзакции в распределенных системах.е2 Phase Commit. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;===* [[Транзакции в распределённых системах]]* [[2 Phase Commit]]
2. Обновления возрастают=== 33 билет.СAP теорема (концепции, подходы, без доказательства)===* [[CAP теорема]]
'''Репликация на основе операций'''=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===* [[Gossip-протоколы]]* [[CRDT]]
Реплика посылает не все состояние, а только обновление всем репликам=== 35 билет. Согласованность можно гарантировать, если обновления коммутативныСамостабилизирующиеся алгоритмы. Кроме того, требуется чтобы каждая операция была доставлена ровно один разИдея.Алгоритмы взаимного исключения и поиска остовного дерева ===* [[Иерархия ошибок в распределённых системах]]todo дельта-CRDT* [[Самостабилизирующиеся алгоритмы]]
rollbackEdits.php mass rollback
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]
* Применение для определения дедлока. Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найден. Рассмотрим два среза: * когда взаимно блокирующие процессы прислали координатору свои графы;* когда они прислали ему notChanged.Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.[[Определение взаимной блокировки]]
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
*[[Общий порядок сообщений]]
*[[Алгоритм Лампорта]]
* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Теорема Фишера-Линча-Патерсона (FLP)]]
===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'' генералов из которых ''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 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
==Ссылки==
<references/>
