Викиконспекты - Вклад участника [ru]

Raft

2019-06-04T08:04:46Z

Yeputons:

[[Категория:Параллельное программирование]]
'''Raft''' — алгоритм для решения задачи [[Replicated State Machine]].
В отличие от [[Paxos]] он не опускает деталей: помимо решения [[Консенсус в распределённой системе|задачи консенсуса]] подробно описывает и выбор лидера, и синхронизацию журнала операций между репликами.

Также одна из целей Raft — быть понятным.
Можно прочитать [http://blog.egrik.ru/2015/10/raft.html беглое описание на русском], посмотреть [http://thesecretlivesofdata.com/raft/ интерактивную презентацию] для введения и посмотреть [https://raft.github.io/ официальный сайт] (с визуализацией и возможностью поиграться) и [https://raft.github.io/raft.pdf исходную статью] (там чётко выписано состояние процессов, все сообщения и правила).

В визуализации точкой помечен <code>matchIndex[]</code> (лидер знает, что до этого места лог follower'а совпадает с логом лидера), а стрелочкой — <code>nextIndex[]</code> (что лидер попробует прислать follower'у).

== Алгоритм ==
=== Состояние узлов ===
=== Выбор лидера ===
=== Репликация логов ===

Raft

2019-06-04T07:44:38Z

Yeputons:

[[Категория:Параллельное программирование]]
'''Raft''' — алгоритм для решения задачи [[Replicated State Machine]].
В отличие от [[Paxos]] он не опускает деталей: помимо решения [[Консенсус в распределённой системе|задачи консенсуса]] подробно описывает и выбор лидера, и синхронизацию журнала операций между репликами.

Также одна из целей Raft — быть понятным.
Можно прочитать [http://blog.egrik.ru/2015/10/raft.html беглое описание на русском], посмотреть [http://thesecretlivesofdata.com/raft/ интерактивную презентацию] для введения и посмотреть [https://raft.github.io/ официальный сайт] (с визуализацией и возможностью поиграться) и [https://raft.github.io/raft.pdf исходную статью] (там чётко выписано состояние процессов, все сообщения и правила).

== Алгоритм ==
=== Состояние узлов ===
=== Выбор лидера ===
=== Репликация логов ===

Raft

2019-06-04T07:43:25Z

Yeputons: /* Алгоритм */

Raft

2019-06-04T07:41:23Z

Yeputons:

Raft

2019-06-04T07:26:31Z

Yeputons: Новая страница: «Категория:Параллельное программирование '''Raft''' — алгоритм для решения задачи Replicated S…»

Paxos

2019-06-04T07:23:28Z

Yeputons:

[[Категория:Параллельное программирование]]
'''Paxos''' — алгоритм [[Консенсус в распределённой системе|консенсуса в распределённой системе]], который детерминированно работает в асинхронной системе с отказами узлов, гарантирует корректный консенсус, но не гарантирует, что тот при наличии отказов будет достигнут на конечное время.

Это первый придуманный практический алгоритм консенсуса такого вида.
Он быстро работает и не приходит к согласию в очень редких случаях, на практике такого не случается.

Описан много где разными словами<ref>https://habr.com/ru/post/346180/</ref><ref>https://lamport.azurewebsites.net/pubs/paxos-simple.pdf</ref><ref>https://en.wikipedia.org/wiki/Paxos_(computer_science)#Basic_Paxos</ref><ref>https://habr.com/ru/post/222825/</ref>.
Обычно используется для хранения самых-самых важных данных.

Тут довольно много деталей опущено, так что реализовать это на практике довольно сложно<ref>https://doi.org/10.1145/1281100.1281103</ref>.

== Алгоритм ==
=== Роли ===
Мы хотим достичь согласованного консенсуса.
У нас есть несколько процессов, у каждого есть некоторое подмножество ролей:
* Предлагающий (proposer) — может выдвинуть предложение
* Принимающий (acceptor) — принимают консенсус
* Узнающий (learner) — тот, кто узнаёт про принятый консенсус
Дальше алгоритм говорит исключительно про роли, а не процессы.
Обычно в каждом процессе совмещаются все три роли.

У алгоритма статическая конфигурация: в базовой версии мы не можем добавлять новые роли в процессе работы.
Переконфигурация — отдельная интересная инженерная задача.

=== Лидер ===
Если у нас только один принимающий процесс, то всё просто, но нет защиты от отказов.
По этому должно быть несколько принимающих процессов.
Алгоритм Paxos требует, чтобы решение принималось [[Кворум|кворумом]] процессов.
Обычно берут кворум простого большинства и 3-5 процессов, выбирают из соображений надёжности: процесс может уйти в swap и это нестрашно (система-то асинхронная), а может полностью отказать (тогда его надо физически заменить).

На самом деле мы не пытаемся сразу принять консенсус, а сначала [[Переформулировки консенсуса в распределённой системе#Выбор лидера|выбираем лидера]],
что эквивалентно консенсусу, но зато потом можно очень быстро работать, если никто не падает.
Лидера выбираем из предлагающих процессов (судя по статье на Хабре, а в лекции говорилось, что из принимающих).

Лидера можно просто и быстро выбрать, если нет отказов.
А если есть — можно просто и быстро выбрать (предположив синхронность системы), но, возможно, будет несколько лидеров.
Тем не менее, Paxos всё ещё будет гарантировать согласие и в этом случае.
Возможно, будет работать бесконечно долго, но согласие будет.

А на практике для получения нескольких лидеров надо, чтобы что-то пошло не так ровно в момент выборов лидера, а это очень быстрый процесс.
Так что на практике лидер почти всегда один и всё работает.

=== Алгоритм ===
К консенсусу мы приходим за несколько голосований.
Каждое голосование инициирует лидер (возможно, несколько лидеров параллельно, если нам не повезло).

У каждого голосования есть уникальный номер $k$: нам требуется, чтобы они в голосованиях были уникальны и возрастали.
Этого можно достичь, если номер — это пара из [[Логические часы Лампорта|логических часов]] и фиксированного уникального номера процесса.
Можно не гонять логические часы на вообще все сообщения, а строить их только на известных процессу номерах голосований, тоже пойдёт.

Примерная схема: на фазе 1 лидер добивается от кворума принимающих ''обещание'', что они за него, а на фазе 2 выбирает какое-то предложение и рассылает его своим принимающим.
У принимающего есть две независимых компоненты состояния: кому он что-нибудь ''пообещал'' (только лидер и номер голосования) и какое предложение он ''принял'' (от какого лидера, номер голосования, какое значение).

'''Фаза 1a (подготовка)''': лидер посылает сообщение $(1a, k)$ всем принимающим (и ждёт ответа от кворума на второй фазе). Пока никаких предложений нет.

'''Фаза 1b (обещание)''': каждый принимающий начинает выбирать предложение с максимальным номером:
# Если пришло предложение больше, чем все предыдущие, то принимающий ''обещает'' лидеру не принимать предложения с меньшим номером, отвечает $(1b, k, ack, 0, 0)$.
Но если какое-то предложение с меньшим номером $k'$ уже было ''принято'' со значением $v'$ (это происходит на фазе 2), то отвечает $(1b, k, ack, k', v')$, чтобы лидер был в курсе.
# Если пришло предложение меньше, чем имеющийся максимум $k''$, ничего не делаем. Ну, можем ответить $(1b, k', nack)$ для оптимизации.
Если лидер видит хотя бы один nack, то он понимает, что его обогнали, и начинает фазу 1 заново, подняв своё $k$ до присланного $k'+1$ (это просто оптимизация, чтобы не тормозить с перевыбором лидера).
Таким образом, если у нас несколько лидеров, они будут друг другу активно мешать.
То есть они в какой-то момент как-то должны догадаться, что их много (как?).

'''Фаза 2a (запрос)''': если лидеру удалось собрать кворум обещаний, то он должен попросить принимающих ''принять'' какое-то значение.
Если ему кто-то сказал, что уже принял значение $v_1$, $v_2$, ..., то выбираем значение с максимальным номером голосования.
А если никто ничего не принимал, то лидер вносит своё предложение.
После этого рассылает предложение принимающим, хотя бы кворуму: $(2a, k, v)$, где $v$ — выбранное лидером предложение.

'''Фаза 2b (подтверждение''': если принимающий получает запрос $(2a, k, v)$ и он ещё не дал обещание для $k' > k$, то он ''принимает'' предложение $(k, v)$ и посылает сообщение $(2b, k, v)$ всем узнающим.
После этого во всех следующих голосованиях всем существующим лидерам принимающий будет сообщать лидеру, что он уже принял какое-то предложение.
А лидер будет пытаться это мнение учитывать.

Узнающий принимает решение: если он получил одинаковое сообщение $(2b, k, v)$ от кворума принимающих, то алгоритм Paxos выбрал значение $v$.

==== Обработка отказов ====
Обычно делается таймаутами(?) и рандомом(?):
* Если лидеру не удалось собрать консенсус за какое-то время, он может забить и попробовать ещё раз.
* Если какой-то узел давно не слышал от лидера, он может инициировать перевыбора
* Если лидер увидел второго лидера, можно выбрать, кому жить (например, тому, у кого номер голосования меньше)

Все эти трюки на корректность не влияют(?) и в каком-то смысле вторичны по сравнению с ядром Paxos.
Но на практике работают хорошо, сбои-то у нас редкие.

==== Количество сообщений ====
На каждый консенсус у нас задержка хотя бы в четыре сообщения: 1a, 1b, 2a, 2b.

==== Наблюдения про корректность ====
Paxos гарантирует, что если было в конце было выбрано значение $v$, то никакое другое никогда больше не может быть выбрано.
В самом деле: если у нас получилось сообщение $(2b, k, v)$ от одного кворума принимающих и сообщение $(2b, k', v')$ от другого кворума принимающих, то эти кворумы пересекаются по принимающему $P$.
Не умаляя общности считаем, что $k < k'$.

Тогда получаем, что $P$ сначала в голосовании $k$ принял от лидера предложение $v$, а потом в голосовании $k' > k$ сообщил об этом лидеру, но тот всё равно выбрал не $v$, а $v'$.
Значит, $v'$ было получено от какого-то принимающего с комментарием "я принял его в голосовании $k'' > k$"

== Модификации ==
Переконфигурация — отдельная задача.

=== Multi paxos ===
Если нам нужно прийти к нескольким консенсусам, то можно вместо запуска нескольких копий Paxos выполнить выбор лидера и первую фазу один раз для всех копий сразу.
Тогда в них будут одинаковые голосования, но они всё ещё будут работать.
Зато сильно сокращается задержка.

=== Fast Paxos ===

=== Dynamic Paxos ===
Можно добавить отдельную операцию "изменение конфигурации" в RSM.

=== Cheap Paxos ===
Если мы хотим пережить много отказов и нам нужно много процессов, то базовый Paxos посылает сообщение всем и ждёт кворума.
Работает быстро, но шлёт много сообщений.
Можно сначала слать только какому-то конкретному элементу кворума, а остальных игнорировать.
И подключать остальных только если кворум долго не отвечает.

В обычном режиме будет меньше сообщений, но при сбоях увеличивается задержка (потому что нужно обнаружить сбой и подключить лежащие в стороне процессы).

Paxos

2019-06-04T07:21:50Z

Yeputons: /* Модификации */

[[Категория:Параллельное программирование]]
'''Paxos''' — алгоритм [[Консенсус в распределённой системе|консенсуса в распределённой системе]], который детерминированно работает в асинхронной системе с отказами узлов, гарантирует корректный консенсус, но не гарантирует, что тот при наличии отказов будет достигнут на конечное время.

Это первый придуманный практический алгоритм консенсуса такого вида.
Он быстро работает и не приходит к согласию в очень редких случаях, на практике такого не случается.

Описан много где разными словами<ref>https://habr.com/ru/post/346180/</ref><ref>https://lamport.azurewebsites.net/pubs/paxos-simple.pdf</ref><ref>https://en.wikipedia.org/wiki/Paxos_(computer_science)#Basic_Paxos</ref><ref>https://habr.com/ru/post/222825/</ref>.
Обычно используется для хранения самых-самых важных данных.

== Алгоритм ==
=== Роли ===
Мы хотим достичь согласованного консенсуса.
У нас есть несколько процессов, у каждого есть некоторое подмножество ролей:
* Предлагающий (proposer) — может выдвинуть предложение
* Принимающий (acceptor) — принимают консенсус
* Узнающий (learner) — тот, кто узнаёт про принятый консенсус
Дальше алгоритм говорит исключительно про роли, а не процессы.
Обычно в каждом процессе совмещаются все три роли.

У алгоритма статическая конфигурация: в базовой версии мы не можем добавлять новые роли в процессе работы.
Переконфигурация — отдельная интересная инженерная задача.

=== Лидер ===
Если у нас только один принимающий процесс, то всё просто, но нет защиты от отказов.
По этому должно быть несколько принимающих процессов.
Алгоритм Paxos требует, чтобы решение принималось [[Кворум|кворумом]] процессов.
Обычно берут кворум простого большинства и 3-5 процессов, выбирают из соображений надёжности: процесс может уйти в swap и это нестрашно (система-то асинхронная), а может полностью отказать (тогда его надо физически заменить).

На самом деле мы не пытаемся сразу принять консенсус, а сначала [[Переформулировки консенсуса в распределённой системе#Выбор лидера|выбираем лидера]],
что эквивалентно консенсусу, но зато потом можно очень быстро работать, если никто не падает.
Лидера выбираем из предлагающих процессов (судя по статье на Хабре, а в лекции говорилось, что из принимающих).

Лидера можно просто и быстро выбрать, если нет отказов.
А если есть — можно просто и быстро выбрать (предположив синхронность системы), но, возможно, будет несколько лидеров.
Тем не менее, Paxos всё ещё будет гарантировать согласие и в этом случае.
Возможно, будет работать бесконечно долго, но согласие будет.

А на практике для получения нескольких лидеров надо, чтобы что-то пошло не так ровно в момент выборов лидера, а это очень быстрый процесс.
Так что на практике лидер почти всегда один и всё работает.

=== Алгоритм ===
К консенсусу мы приходим за несколько голосований.
Каждое голосование инициирует лидер (возможно, несколько лидеров параллельно, если нам не повезло).

У каждого голосования есть уникальный номер $k$: нам требуется, чтобы они в голосованиях были уникальны и возрастали.
Этого можно достичь, если номер — это пара из [[Логические часы Лампорта|логических часов]] и фиксированного уникального номера процесса.
Можно не гонять логические часы на вообще все сообщения, а строить их только на известных процессу номерах голосований, тоже пойдёт.

Примерная схема: на фазе 1 лидер добивается от кворума принимающих ''обещание'', что они за него, а на фазе 2 выбирает какое-то предложение и рассылает его своим принимающим.
У принимающего есть две независимых компоненты состояния: кому он что-нибудь ''пообещал'' (только лидер и номер голосования) и какое предложение он ''принял'' (от какого лидера, номер голосования, какое значение).

'''Фаза 1a (подготовка)''': лидер посылает сообщение $(1a, k)$ всем принимающим (и ждёт ответа от кворума на второй фазе). Пока никаких предложений нет.

'''Фаза 1b (обещание)''': каждый принимающий начинает выбирать предложение с максимальным номером:
# Если пришло предложение больше, чем все предыдущие, то принимающий ''обещает'' лидеру не принимать предложения с меньшим номером, отвечает $(1b, k, ack, 0, 0)$.
Но если какое-то предложение с меньшим номером $k'$ уже было ''принято'' со значением $v'$ (это происходит на фазе 2), то отвечает $(1b, k, ack, k', v')$, чтобы лидер был в курсе.
# Если пришло предложение меньше, чем имеющийся максимум $k''$, ничего не делаем. Ну, можем ответить $(1b, k', nack)$ для оптимизации.
Если лидер видит хотя бы один nack, то он понимает, что его обогнали, и начинает фазу 1 заново, подняв своё $k$ до присланного $k'+1$ (это просто оптимизация, чтобы не тормозить с перевыбором лидера).
Таким образом, если у нас несколько лидеров, они будут друг другу активно мешать.
То есть они в какой-то момент как-то должны догадаться, что их много (как?).

'''Фаза 2a (запрос)''': если лидеру удалось собрать кворум обещаний, то он должен попросить принимающих ''принять'' какое-то значение.
Если ему кто-то сказал, что уже принял значение $v_1$, $v_2$, ..., то выбираем значение с максимальным номером голосования.
А если никто ничего не принимал, то лидер вносит своё предложение.
После этого рассылает предложение принимающим, хотя бы кворуму: $(2a, k, v)$, где $v$ — выбранное лидером предложение.

'''Фаза 2b (подтверждение''': если принимающий получает запрос $(2a, k, v)$ и он ещё не дал обещание для $k' > k$, то он ''принимает'' предложение $(k, v)$ и посылает сообщение $(2b, k, v)$ всем узнающим.
После этого во всех следующих голосованиях всем существующим лидерам принимающий будет сообщать лидеру, что он уже принял какое-то предложение.
А лидер будет пытаться это мнение учитывать.

Узнающий принимает решение: если он получил одинаковое сообщение $(2b, k, v)$ от кворума принимающих, то алгоритм Paxos выбрал значение $v$.

==== Обработка отказов ====
Обычно делается таймаутами(?) и рандомом(?):
* Если лидеру не удалось собрать консенсус за какое-то время, он может забить и попробовать ещё раз.
* Если какой-то узел давно не слышал от лидера, он может инициировать перевыбора
* Если лидер увидел второго лидера, можно выбрать, кому жить (например, тому, у кого номер голосования меньше)

Все эти трюки на корректность не влияют(?) и в каком-то смысле вторичны по сравнению с ядром Paxos.
Но на практике работают хорошо, сбои-то у нас редкие.

==== Количество сообщений ====
На каждый консенсус у нас задержка хотя бы в четыре сообщения: 1a, 1b, 2a, 2b.

==== Наблюдения про корректность ====
Paxos гарантирует, что если было в конце было выбрано значение $v$, то никакое другое никогда больше не может быть выбрано.
В самом деле: если у нас получилось сообщение $(2b, k, v)$ от одного кворума принимающих и сообщение $(2b, k', v')$ от другого кворума принимающих, то эти кворумы пересекаются по принимающему $P$.
Не умаляя общности считаем, что $k < k'$.

Тогда получаем, что $P$ сначала в голосовании $k$ принял от лидера предложение $v$, а потом в голосовании $k' > k$ сообщил об этом лидеру, но тот всё равно выбрал не $v$, а $v'$.
Значит, $v'$ было получено от какого-то принимающего с комментарием "я принял его в голосовании $k'' > k$"

== Модификации ==
Переконфигурация — отдельная задача.

=== Multi paxos ===
Если нам нужно прийти к нескольким консенсусам, то можно вместо запуска нескольких копий Paxos выполнить выбор лидера и первую фазу один раз для всех копий сразу.
Тогда в них будут одинаковые голосования, но они всё ещё будут работать.
Зато сильно сокращается задержка.

=== Fast Paxos ===

=== Dynamic Paxos ===
Можно добавить отдельную операцию "изменение конфигурации" в RSM.

=== Cheap Paxos ===
Если мы хотим пережить много отказов и нам нужно много процессов, то базовый Paxos посылает сообщение всем и ждёт кворума.
Работает быстро, но шлёт много сообщений.
Можно сначала слать только какому-то конкретному элементу кворума, а остальных игнорировать.
И подключать остальных только если кворум долго не отвечает.

В обычном режиме будет меньше сообщений, но при сбоях увеличивается задержка (потому что нужно обнаружить сбой и подключить лежащие в стороне процессы).

Paxos

2019-06-04T07:20:08Z

Yeputons: /* Алгоритм */

[[Категория:Параллельное программирование]]
'''Paxos''' — алгоритм [[Консенсус в распределённой системе|консенсуса в распределённой системе]], который детерминированно работает в асинхронной системе с отказами узлов, гарантирует корректный консенсус, но не гарантирует, что тот при наличии отказов будет достигнут на конечное время.

Это первый придуманный практический алгоритм консенсуса такого вида.
Он быстро работает и не приходит к согласию в очень редких случаях, на практике такого не случается.

Описан много где разными словами<ref>https://habr.com/ru/post/346180/</ref><ref>https://lamport.azurewebsites.net/pubs/paxos-simple.pdf</ref><ref>https://en.wikipedia.org/wiki/Paxos_(computer_science)#Basic_Paxos</ref><ref>https://habr.com/ru/post/222825/</ref>.
Обычно используется для хранения самых-самых важных данных.

== Алгоритм ==
=== Роли ===
Мы хотим достичь согласованного консенсуса.
У нас есть несколько процессов, у каждого есть некоторое подмножество ролей:
* Предлагающий (proposer) — может выдвинуть предложение
* Принимающий (acceptor) — принимают консенсус
* Узнающий (learner) — тот, кто узнаёт про принятый консенсус
Дальше алгоритм говорит исключительно про роли, а не процессы.
Обычно в каждом процессе совмещаются все три роли.

У алгоритма статическая конфигурация: в базовой версии мы не можем добавлять новые роли в процессе работы.
Переконфигурация — отдельная интересная инженерная задача.

=== Лидер ===
Если у нас только один принимающий процесс, то всё просто, но нет защиты от отказов.
По этому должно быть несколько принимающих процессов.
Алгоритм Paxos требует, чтобы решение принималось [[Кворум|кворумом]] процессов.
Обычно берут кворум простого большинства и 3-5 процессов, выбирают из соображений надёжности: процесс может уйти в swap и это нестрашно (система-то асинхронная), а может полностью отказать (тогда его надо физически заменить).

На самом деле мы не пытаемся сразу принять консенсус, а сначала [[Переформулировки консенсуса в распределённой системе#Выбор лидера|выбираем лидера]],
что эквивалентно консенсусу, но зато потом можно очень быстро работать, если никто не падает.
Лидера выбираем из предлагающих процессов (судя по статье на Хабре, а в лекции говорилось, что из принимающих).

Лидера можно просто и быстро выбрать, если нет отказов.
А если есть — можно просто и быстро выбрать (предположив синхронность системы), но, возможно, будет несколько лидеров.
Тем не менее, Paxos всё ещё будет гарантировать согласие и в этом случае.
Возможно, будет работать бесконечно долго, но согласие будет.

А на практике для получения нескольких лидеров надо, чтобы что-то пошло не так ровно в момент выборов лидера, а это очень быстрый процесс.
Так что на практике лидер почти всегда один и всё работает.

=== Алгоритм ===
К консенсусу мы приходим за несколько голосований.
Каждое голосование инициирует лидер (возможно, несколько лидеров параллельно, если нам не повезло).

У каждого голосования есть уникальный номер $k$: нам требуется, чтобы они в голосованиях были уникальны и возрастали.
Этого можно достичь, если номер — это пара из [[Логические часы Лампорта|логических часов]] и фиксированного уникального номера процесса.
Можно не гонять логические часы на вообще все сообщения, а строить их только на известных процессу номерах голосований, тоже пойдёт.

Примерная схема: на фазе 1 лидер добивается от кворума принимающих ''обещание'', что они за него, а на фазе 2 выбирает какое-то предложение и рассылает его своим принимающим.
У принимающего есть две независимых компоненты состояния: кому он что-нибудь ''пообещал'' (только лидер и номер голосования) и какое предложение он ''принял'' (от какого лидера, номер голосования, какое значение).

'''Фаза 1a (подготовка)''': лидер посылает сообщение $(1a, k)$ всем принимающим (и ждёт ответа от кворума на второй фазе). Пока никаких предложений нет.

'''Фаза 1b (обещание)''': каждый принимающий начинает выбирать предложение с максимальным номером:
# Если пришло предложение больше, чем все предыдущие, то принимающий ''обещает'' лидеру не принимать предложения с меньшим номером, отвечает $(1b, k, ack, 0, 0)$.
Но если какое-то предложение с меньшим номером $k'$ уже было ''принято'' со значением $v'$ (это происходит на фазе 2), то отвечает $(1b, k, ack, k', v')$, чтобы лидер был в курсе.
# Если пришло предложение меньше, чем имеющийся максимум $k''$, ничего не делаем. Ну, можем ответить $(1b, k', nack)$ для оптимизации.
Если лидер видит хотя бы один nack, то он понимает, что его обогнали, и начинает фазу 1 заново, подняв своё $k$ до присланного $k'+1$ (это просто оптимизация, чтобы не тормозить с перевыбором лидера).
Таким образом, если у нас несколько лидеров, они будут друг другу активно мешать.
То есть они в какой-то момент как-то должны догадаться, что их много (как?).

'''Фаза 2a (запрос)''': если лидеру удалось собрать кворум обещаний, то он должен попросить принимающих ''принять'' какое-то значение.
Если ему кто-то сказал, что уже принял значение $v_1$, $v_2$, ..., то выбираем значение с максимальным номером голосования.
А если никто ничего не принимал, то лидер вносит своё предложение.
После этого рассылает предложение принимающим, хотя бы кворуму: $(2a, k, v)$, где $v$ — выбранное лидером предложение.

'''Фаза 2b (подтверждение''': если принимающий получает запрос $(2a, k, v)$ и он ещё не дал обещание для $k' > k$, то он ''принимает'' предложение $(k, v)$ и посылает сообщение $(2b, k, v)$ всем узнающим.
После этого во всех следующих голосованиях всем существующим лидерам принимающий будет сообщать лидеру, что он уже принял какое-то предложение.
А лидер будет пытаться это мнение учитывать.

Узнающий принимает решение: если он получил одинаковое сообщение $(2b, k, v)$ от кворума принимающих, то алгоритм Paxos выбрал значение $v$.

==== Обработка отказов ====
Обычно делается таймаутами(?) и рандомом(?):
* Если лидеру не удалось собрать консенсус за какое-то время, он может забить и попробовать ещё раз.
* Если какой-то узел давно не слышал от лидера, он может инициировать перевыбора
* Если лидер увидел второго лидера, можно выбрать, кому жить (например, тому, у кого номер голосования меньше)

Все эти трюки на корректность не влияют(?) и в каком-то смысле вторичны по сравнению с ядром Paxos.
Но на практике работают хорошо, сбои-то у нас редкие.

==== Количество сообщений ====
На каждый консенсус у нас задержка хотя бы в четыре сообщения: 1a, 1b, 2a, 2b.

==== Наблюдения про корректность ====
Paxos гарантирует, что если было в конце было выбрано значение $v$, то никакое другое никогда больше не может быть выбрано.
В самом деле: если у нас получилось сообщение $(2b, k, v)$ от одного кворума принимающих и сообщение $(2b, k', v')$ от другого кворума принимающих, то эти кворумы пересекаются по принимающему $P$.
Не умаляя общности считаем, что $k < k'$.

Тогда получаем, что $P$ сначала в голосовании $k$ принял от лидера предложение $v$, а потом в голосовании $k' > k$ сообщил об этом лидеру, но тот всё равно выбрал не $v$, а $v'$.
Значит, $v'$ было получено от какого-то принимающего с комментарием "я принял его в голосовании $k'' > k$"

== Модификации ==

Paxos

2019-06-04T07:16:53Z

Yeputons: /* Алгоритм */

[[Категория:Параллельное программирование]]
'''Paxos''' — алгоритм [[Консенсус в распределённой системе|консенсуса в распределённой системе]], который детерминированно работает в асинхронной системе с отказами узлов, гарантирует корректный консенсус, но не гарантирует, что тот при наличии отказов будет достигнут на конечное время.

Это первый придуманный практический алгоритм консенсуса такого вида.
Он быстро работает и не приходит к согласию в очень редких случаях, на практике такого не случается.

Описан много где разными словами<ref>https://habr.com/ru/post/346180/</ref><ref>https://lamport.azurewebsites.net/pubs/paxos-simple.pdf</ref><ref>https://en.wikipedia.org/wiki/Paxos_(computer_science)#Basic_Paxos</ref><ref>https://habr.com/ru/post/222825/</ref>.
Обычно используется для хранения самых-самых важных данных.

== Алгоритм ==
=== Роли ===
Мы хотим достичь согласованного консенсуса.
У нас есть несколько процессов, у каждого есть некоторое подмножество ролей:
* Предлагающий (proposer) — может выдвинуть предложение
* Принимающий (acceptor) — принимают консенсус
* Узнающий (learner) — тот, кто узнаёт про принятый консенсус
Дальше алгоритм говорит исключительно про роли, а не процессы.
Обычно в каждом процессе совмещаются все три роли.

У алгоритма статическая конфигурация: в базовой версии мы не можем добавлять новые роли в процессе работы.
Переконфигурация — отдельная интересная инженерная задача.

=== Лидер ===
Если у нас только один принимающий процесс, то всё просто, но нет защиты от отказов.
По этому должно быть несколько принимающих процессов.
Алгоритм Paxos требует, чтобы решение принималось [[Кворум|кворумом]] процессов.
Обычно берут кворум простого большинства и 3-5 процессов, выбирают из соображений надёжности: процесс может уйти в swap и это нестрашно (система-то асинхронная), а может полностью отказать (тогда его надо физически заменить).

На самом деле мы не пытаемся сразу принять консенсус, а сначала [[Переформулировки консенсуса в распределённой системе#Выбор лидера|выбираем лидера]],
что эквивалентно консенсусу, но зато потом можно очень быстро работать, если никто не падает.
Лидера выбираем из предлагающих процессов (судя по статье на Хабре, а в лекции говорилось, что из принимающих).

Лидера можно просто и быстро выбрать, если нет отказов.
А если есть — можно просто и быстро выбрать (предположив синхронность системы), но, возможно, будет несколько лидеров.
Тем не менее, Paxos всё ещё будет гарантировать согласие и в этом случае.
Возможно, будет работать бесконечно долго, но согласие будет.

А на практике для получения нескольких лидеров надо, чтобы что-то пошло не так ровно в момент выборов лидера, а это очень быстрый процесс.
Так что на практике лидер почти всегда один и всё работает.

=== Алгоритм ===
К консенсусу мы приходим за несколько голосований.
Каждое голосование инициирует лидер (возможно, несколько лидеров параллельно, если нам не повезло).

У каждого голосования есть уникальный номер $k$: нам требуется, чтобы они в голосованиях были уникальны и возрастали.
Этого можно достичь, если номер — это пара из [[Логические часы Лампорта|логических часов]] и фиксированного уникального номера процесса.
Можно не гонять логические часы на вообще все сообщения, а строить их только на известных процессу номерах голосований, тоже пойдёт.

Примерная схема: на фазе 1 лидер добивается от кворума принимающих ''обещание'', что они за него, а на фазе 2 выбирает какое-то предложение и рассылает его своим принимающим.
У принимающего есть две независимых компоненты состояния: кому он что-нибудь ''пообещал'' (только лидер и номер голосования) и какое предложение он ''принял'' (от какого лидера, номер голосования, какое значение).

'''Фаза 1a (подготовка)''': лидер посылает сообщение $(1a, k)$ кворуму принимающих (или вообще всем, а ждёт ответа от кворума?). Пока никаких предложений нет.

'''Фаза 1b (обещание)''': каждый принимающий начинает выбирать предложение с максимальным номером:
# Если пришло предложение больше, чем все предыдущие, то принимающий ''обещает'' лидеру не принимать предложения с меньшим номером, отвечает $(1b, k, ack, 0, 0)$.
Но если какое-то предложение с меньшим номером $k'$ уже было ''принято'' со значением $v'$ (это происходит на фазе 2), то отвечает $(1b, k, ack, k', v')$, чтобы лидер был в курсе.
# Если пришло предложение меньше, чем имеющийся максимум $k''$, ничего не делаем. Ну, можем ответить $(1b, k', nack)$ для оптимизации.
Если лидер видит хотя бы один nack, то он понимает, что его обогнали, и начинает фазу 1 заново, подняв своё $k$ до присланного $k'+1$ (это просто оптимизация, чтобы не тормозить с перевыбором лидера).
Таким образом, если у нас несколько лидеров, они будут друг другу активно мешать.
То есть они в какой-то момент как-то должны догадаться, что их много (как?).

'''Фаза 2a (запрос)''': если лидеру удалось собрать кворум обещаний, то он должен попросить принимающих ''принять'' какое-то значение.
Если ему кто-то сказал, что уже принял значение $v_1$, $v_2$, ..., то выбираем значение с максимальным номером голосования.
А если никто ничего не принимал, то лидер вносит своё предложение.
После этого рассылает предложение принимающим, хотя бы кворуму: $(2a, k, v)$, где $v$ — выбранное лидером предложение.

'''Фаза 2b (подтверждение''': если принимающий получает запрос $(2a, k, v)$ и он ещё не дал обещание для $k' > k$, то он ''принимает'' предложение $(k, v)$ и посылает сообщение $(2b, k, v)$ всем узнающим.
После этого во всех следующих голосованиях всем существующим лидерам принимающий будет сообщать лидеру, что он уже принял какое-то предложение.
А лидер будет пытаться это мнение учитывать.

Узнающий принимает решение: если он получил одинаковое сообщение $(2b, k, v)$ от кворума принимающих, то алгоритм Paxos выбрал значение $v$.

==== Обработка отказов ====
Обычно делается таймаутами(?) и рандомом(?):
* Если лидеру не удалось собрать консенсус за какое-то время, он может забить и попробовать ещё раз.
* Если какой-то узел давно не слышал от лидера, он может инициировать перевыбора
* Если лидер увидел второго лидера, можно выбрать, кому жить (например, тому, у кого номер голосования меньше)

Все эти трюки на корректность не влияют(?) и в каком-то смысле вторичны по сравнению с ядром Paxos.
Но на практике работают хорошо, сбои-то у нас редкие.

==== Количество сообщений ====
На каждый консенсус у нас задержка хотя бы в четыре сообщения: 1a, 1b, 2a, 2b.

==== Наблюдения про корректность ====
Paxos гарантирует, что если было в конце было выбрано значение $v$, то никакое другое никогда больше не может быть выбрано.
В самом деле: если у нас получилось сообщение $(2b, k, v)$ от одного кворума принимающих и сообщение $(2b, k', v')$ от другого кворума принимающих, то эти кворумы пересекаются по принимающему $P$.
Не умаляя общности считаем, что $k < k'$.

Тогда получаем, что $P$ сначала в голосовании $k$ принял от лидера предложение $v$, а потом в голосовании $k' > k$ сообщил об этом лидеру, но тот всё равно выбрал не $v$, а $v'$.
Значит, $v'$ было получено от какого-то принимающего с комментарием "я принял его в голосовании $k'' > k$"

== Модификации ==

Paxos

2019-06-04T07:04:05Z

Yeputons:

Paxos

2019-06-04T06:19:10Z

Yeputons:

Paxos

2019-06-04T06:18:16Z

Yeputons:

Replicated State Machine

2019-06-04T06:17:04Z

Yeputons:

[[Категория:Параллельное программирование]]
'''Replicated State Machine''' — система, которая хранит некий автомат (state machine) распределённо, а пользователи могут применять к этому автомату операции.
После этого RSM обязана эту операцию либо атомарно применить, либо откатить, и сообщить об этом пользователю.
Подтверждённые пользователю транзакции теряться не должны.

Это может быть полезно, когда у нас есть очень важные данные, которые надо:
# Защитить от сбоев любого конкретного узла (т.е. надо хранить на нескольких узлах и нельзя иметь центрального координатора)
# Быстро обновлять (т.е. нельзя просто записывать на диск каждый раз)

Если операции, применяемые к состоянию, детерминированы, то можно не клонировать состояние между машинами, а просто применять операции повторно на разных узлах.
Но операции обычно не коммутируют, поэтому всем узлам надо приходить к консенсусу: какие операции в каком порядке применять.

Теоретически эта задача считается эквивалентной задаче консенсуса, поэтому действуют ограничения [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]].
Нам обязательно нужна защита от отказов (иначе непонятно, зачем клонировать автомат),
рандом из [[Алгоритм Бен-Ора|алгоритма Бен-Ора]] "не сильно спасает" (как говорилось на лекции; вероятно, тут подразумевается его тормознутость),
а надеяться на синхронность системы на практике не хочется ("вдруг сообщение придёт не скоро? или в swap кто-то ушёл" с лекции).
По этому поводу мы обычно жертвуем завершением за конечное время: алгоритм [[Paxos]].

Однако на практике могут возникать дополнительные сложности с тем, что узлы у нас не падают навсегда, а временно уходят и поднимаются обратно (т.е. [[Иерархия ошибок в распределённых системах|с точки зрения теории]] у нас, строго говоря, ненадёжная доставка сообщений), а нам надо консенсус запускать несколько раз и ещё как-то доносить старые решения до вернувшихся узлов (чтобы на них тоже получилось корректное состояние).
В алгоритме [[Raft]] это отдельно разбирается.

По факту применяются и [[Paxos]], и [[Raft]] и все живут.

Paxos

2019-06-04T06:13:18Z

Yeputons: Новая страница: «Категория:Параллельное программирование '''Paxos''' — алгоритм Консенсус в распределённ…»

Replicated State Machine

2019-06-04T06:08:03Z

Yeputons:

[[Категория:Параллельное программирование]]
'''Replicated State Machine''' — система, которая хранит некий автомат (state machine) распределённо, а пользователи могут применять к этому автомату операции.
После этого RSM обязана эту операцию либо атомарно применить, либо откатить, и сообщить об этом пользователю.
Подтверждённые пользователю транзакции теряться не должны.

Это может быть полезно, когда у нас есть очень важные данные, которые надо:
# Защитить от сбоев любого конкретного узла (т.е. надо хранить на нескольких узлах и нельзя иметь центрального координатора)
# Быстро обновлять (т.е. нельзя просто записывать на диск каждый раз)

Если операции, применяемые к состоянию, детерминированы, то можно не клонировать состояние между машинами, а просто применять операции повторно на разных узлах.
Но операции обычно не коммутируют, поэтому всем узлам надо приходить к консенсусу: какие операции в каком порядке применять.

Теоретически эта задача считается эквивалентной задаче консенсуса, поэтому действуют ограничения [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]].
Нам обязательно нужна защита от отказов (иначе непонятно, зачем клонировать автомат),
рандом из [[Алгоритм Бен-Ора|алгоритма Бен-Ора]] "не сильно спасает" (как говорилось на лекции; вероятно, тут подразумевается его тормознутость),
а надеяться на синхронность системы на практике не хочется ("вдруг сообщение придёт не скоро?" с лекции).
По этому поводу мы обычно жертвуем завершением за конечное время: алгоритм [[Paxos]].

Однако на практике могут возникать дополнительные сложности с тем, что узлы у нас не падают навсегда, а временно уходят и поднимаются обратно (т.е. [[Иерархия ошибок в распределённых системах|с точки зрения теории]] у нас, строго говоря, ненадёжная доставка сообщений), а нам надо консенсус запускать несколько раз и ещё как-то доносить старые решения до вернувшихся узлов (чтобы на них тоже получилось корректное состояние).
В алгоритме [[Raft]] это отдельно разбирается.

По факту применяются и [[Paxos]], и [[Raft]] и все живут.

Replicated State Machine

2019-06-04T06:07:51Z

Yeputons:

'''Replicated State Machine''' — система, которая хранит некий автомат (state machine) распределённо, а пользователи могут применять к этому автомату операции.
После этого RSM обязана эту операцию либо атомарно применить, либо откатить, и сообщить об этом пользователю.
Подтверждённые пользователю транзакции теряться не должны.

Это может быть полезно, когда у нас есть очень важные данные, которые надо:
# Защитить от сбоев любого конкретного узла (т.е. надо хранить на нескольких узлах и нельзя иметь центрального координатора)
# Быстро обновлять (т.е. нельзя просто записывать на диск каждый раз)

Если операции, применяемые к состоянию, детерминированы, то можно не клонировать состояние между машинами, а просто применять операции повторно на разных узлах.
Но операции обычно не коммутируют, поэтому всем узлам надо приходить к консенсусу: какие операции в каком порядке применять.

Теоретически эта задача считается эквивалентной задаче консенсуса, поэтому действуют ограничения [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]].
Нам обязательно нужна защита от отказов (иначе непонятно, зачем клонировать автомат),
рандом из [[Алгоритм Бен-Ора|алгоритма Бен-Ора]] "не сильно спасает" (как говорилось на лекции; вероятно, тут подразумевается его тормознутость),
а надеяться на синхронность системы на практике не хочется ("вдруг сообщение придёт не скоро?" с лекции).
По этому поводу мы обычно жертвуем завершением за конечное время: алгоритм [[Paxos]].

Однако на практике могут возникать дополнительные сложности с тем, что узлы у нас не падают навсегда, а временно уходят и поднимаются обратно (т.е. [[Иерархия ошибок в распределённых системах|с точки зрения теории]] у нас, строго говоря, ненадёжная доставка сообщений), а нам надо консенсус запускать несколько раз и ещё как-то доносить старые решения до вернувшихся узлов (чтобы на них тоже получилось корректное состояние).
В алгоритме [[Raft]] это отдельно разбирается.

По факту применяются и [[Paxos]], и [[Raft]] и все живут.

Параллельное программирование

2019-06-04T06:06:16Z

Yeputons: /* 30 билет. Raft. Алгоритм, его свойства. */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
*[[Базовые определения и формализм]]
*[[Алгоритмы взаимного исключения]]
*[[Стек Трайбера]]
*[[Формализм распределённых систем]]

==6 семестр==
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===1-2 билеты. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран)

===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат (WCP)]]
*[[Централизованный алгоритм для WCP]]
*[[Распределенный алгоритм для WCP]]

===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
* [[Диффундирующие вычисления]]
* [[Алгоритм Дейкстры и Шолтена]]

===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]
*[[Определение взаимной блокировки]]

===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
* [[Иерархия порядков сообщений]]
* [[Алгоритм для FIFO порядка]]
* [[Алгоритм для причинно-согласованного порядка]]
* [[Алгоритм для синхронного порядка]]

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

===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===

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

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

===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Консенсус в синхронных системах]]

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

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

=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Алгоритм Бен-Ора]]

=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
* [[Консенсус в распределённой системе]]
* [[Replicated State Machine]]
* [[Paxos]]

=== 30 билет. Raft. Алгоритм, его свойства.===
* [[Консенсус в распределённой системе]]
* [[Replicated State Machine]]
* [[Raft]]

=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
* [[Транзакции в распределённых системах]]
* [[2 Phase Locking]]

=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
* [[Транзакции в распределённых системах]]
* [[2 Phase Commit]]

=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
* [[CAP теорема]]

=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
* [[Gossip-протоколы]]
* [[CRDT]]

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

==Ссылки==
<references/>

Параллельное программирование

2019-06-04T06:06:13Z

Yeputons: /* 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации. */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
*[[Базовые определения и формализм]]
*[[Алгоритмы взаимного исключения]]
*[[Стек Трайбера]]
*[[Формализм распределённых систем]]

==6 семестр==
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===1-2 билеты. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран)

===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат (WCP)]]
*[[Централизованный алгоритм для WCP]]
*[[Распределенный алгоритм для WCP]]

===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
* [[Диффундирующие вычисления]]
* [[Алгоритм Дейкстры и Шолтена]]

===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]
*[[Определение взаимной блокировки]]

===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
* [[Иерархия порядков сообщений]]
* [[Алгоритм для FIFO порядка]]
* [[Алгоритм для причинно-согласованного порядка]]
* [[Алгоритм для синхронного порядка]]

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

===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===

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

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

===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Консенсус в синхронных системах]]

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

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

=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Алгоритм Бен-Ора]]

=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
* [[Консенсус в распределённой системе]]
* [[Replicated State Machine]]
* [[Paxos]]

=== 30 билет. Raft. Алгоритм, его свойства.===
* [[Replicated State Machine]]
* [[Raft]]

=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
* [[Транзакции в распределённых системах]]
* [[2 Phase Locking]]

=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
* [[Транзакции в распределённых системах]]
* [[2 Phase Commit]]

=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
* [[CAP теорема]]

=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
* [[Gossip-протоколы]]
* [[CRDT]]

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

==Ссылки==
<references/>

Параллельное программирование

2019-06-04T06:05:38Z

Yeputons: /* 30 билет. Raft. Алгоритм, его свойства. */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
*[[Базовые определения и формализм]]
*[[Алгоритмы взаимного исключения]]
*[[Стек Трайбера]]
*[[Формализм распределённых систем]]

==6 семестр==
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===1-2 билеты. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран)

===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат (WCP)]]
*[[Централизованный алгоритм для WCP]]
*[[Распределенный алгоритм для WCP]]

===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
* [[Диффундирующие вычисления]]
* [[Алгоритм Дейкстры и Шолтена]]

===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]
*[[Определение взаимной блокировки]]

===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
* [[Иерархия порядков сообщений]]
* [[Алгоритм для FIFO порядка]]
* [[Алгоритм для причинно-согласованного порядка]]
* [[Алгоритм для синхронного порядка]]

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

===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===

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

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

===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Консенсус в синхронных системах]]

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

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

=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Алгоритм Бен-Ора]]

=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
* [[Replicated State Machine]]
* [[Paxos]]

=== 30 билет. Raft. Алгоритм, его свойства.===
* [[Replicated State Machine]]
* [[Raft]]

=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
* [[Транзакции в распределённых системах]]
* [[2 Phase Locking]]

=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
* [[Транзакции в распределённых системах]]
* [[2 Phase Commit]]

=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
* [[CAP теорема]]

=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
* [[Gossip-протоколы]]
* [[CRDT]]

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

==Ссылки==
<references/>

Replicated State Machine

2019-06-04T06:02:56Z

Yeputons: Новая страница: «'''Replicated State Machine''' — система, которая хранит некий автомат (state machine) распределённо, а польз…»

'''Replicated State Machine''' — система, которая хранит некий автомат (state machine) распределённо, а пользователи могут применять к этому автомату операции.
После этого RSM обязана эту операцию либо атомарно применить, либо откатить, и сообщить об этом пользователю.
Подтверждённые пользователю транзакции теряться не должны.

Это может быть полезно, когда у нас есть очень важные данные, которые надо:
# Защитить от сбоев любого конкретного узла (т.е. надо хранить на нескольких узлах и нельзя иметь центрального координатора)
# Быстро обновлять (т.е. нельзя просто записывать на диск каждый раз)

Если операции, применяемые к состоянию, детерминированы, то можно не клонировать состояние между машинами, а просто применять операции повторно на разных узлах.
Но операции обычно не коммутируют, поэтому всем узлам надо приходить к консенсусу: какие операции в каком порядке применять.

Теоретически эта задача считается эквивалентной задаче консенсуса, поэтому действуют ограничения [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]].
Нам обязательно нужна защита от отказов (иначе непонятно, зачем клонировать автомат),
рандом из [[Алгоритм Бен-Ора|алгоритма Бен-Ора]] "не сильно спасает" (как говорилось на лекции; вероятно, тут подразумевается его тормознутость),
а надеяться на синхронность системы на практике не хочется ("вдруг сообщение придёт не скоро?" с лекции).
По этому поводу мы обычно жертвуем завершением за конечное время: алгоритм [[Paxos]].

Однако на практике могут возникать дополнительные сложности с тем, что узлы у нас не падают навсегда, а временно уходят и поднимаются обратно (т.е. [[Иерархия ошибок в распределённых системах|с точки зрения теории]] у нас ненадёжная доставка сообщений), а нам надо консенсус запускать несколько раз и ещё как-то доносить старые решения до вернувшихся узлов (чтобы на них тоже получилось корректное состояние).
В алгоритме [[Raft]] это отдельно разбирается.

Алгоритм Бен-Ора

2019-06-04T05:57:49Z

Yeputons:

[[Категория:Параллельное программирование]]
Алгоритм Бен-Ора — алгоритм, который позволяет $N$ процессам в асинхронной системе прийти к недетерминированному консенсусу на одном бите, если у нас не более $f<\frac N 2$ отказов узлов даже при ''сильном противнике'' за ожидаемое время $O(2^N)$.

Мы хотим, чтобы процессы пришли к консенсусу.
Мы можем разрешить процессам кидать монетку, тем самым добавив недетерминизм и обойдя ограничения [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]] на невозможность консенсуса.

== Модель ==
Состояний у нас бесконечно, поэтому надо как-то уточнить требование завершимости: скажем, что мы хотим достигнуть консенсуса не за конечное время, а с вероятностью 1 (см. теорию меры для формальных определений).

Несмотря на то, что в каждой конфигурации мы теперь находимся лишь с какой-то вероятностью,
порядок доставки сообщений всё ещё выбирает противник, чтобы нам было посложнее.
Бывает принципиально два вида противников:
* '''Сильный противник''' знает всё, что происходило в системе и всех процессах, включая полученные случайные биты, но не может предсказать будущее.
* '''Слабый противник''' чего-то может и не знать. Например, может видеть только сообщения и не знать ни полученных битов, ни внутренние состояния процессов.

Алгоритм Бен-Ора работает даже с сильным противником.

== Алгоритм ==
Каждый процесс работает бесконечно долго, алгоритм делится на одинаковые '''раунды''', пронумерованные натуральными числами с единицы.

Каждый раунд состоит из двух '''фаз'''.
В каждой фазе процесс посылает всем остальным сообщение.
Важно, что система всё равно '''асинхронная''', поэтому для завершения фазы мы
ждём хотя бы $N-f$ ответов (а такое обязательно произойдёт, потому что у нас не более $f$ отказов),
а не какое-то "время" (которого нет).

Каждое сообщение содержит в себе номер раунда, так что если пришло сообщение со старого раунда, оно игнорируется.
Если пришло с нового — ставится в очередь.
Вроде нам даже FIFO не требуется(?).

В каждый момент у процесса есть '''предпочтение''' — бит.

'''Первая фаза''': процесс рассылает всем остальным своё предпочтение: сообщение $(1, k, p)$, где $k$ — это номер раунда, а $p$ — предпочтение.
После получения $N-f$ ответов фаза завершается:
* Если процесс получил строго больше $\frac N 2$ предпочтений (включая своё) с каким-то значением, то это предложение '''ратифицируется'''.

'''Вторая фаза''': если у процесса есть ратифицированное на данном шаге предпочтение, то он рассылает всем остальным
сообщение $(2, k, v)$ для ратификации ($v$ — ратифицированное значение).
В противном случае рассылает всем сообщение $(2, k, ?)$.
После получения $N-f$ ответов фаза завершается:
* Если процесс получил хотя бы одну ратификацию (или сам её отправил), то в следующем раунде предпочтение процесса меняется на полученное ратифицированное кем-то значение (все ратификации совпадают, см. ниже).
* Если процесс получил строго больше $f$ ратификаций, процесс принимает соответствующее ратифицированное решение, но продолжает выполняться в следующих раундах
* Если процесс не получил ни одной ратификации, предпочтение в следующем раунде меняется на случайный бит (это единственное '''недетерминированное место''')

=== Доказательство ===
'''Лемма''': в каждом раунде $k$ все ратифицированные значения одинаковы.
Это очевидно, так как для ратификации требуется набрать строгое большинство предложений.

'''Лемма''': если в раунде $k$ процесс $P$ принял решение $v$, то раунд $k+1$ все процессы начнут с предпочтением $v$.
Доказательство: чтобы принять решение, надо было получить хотя бы $f+1$ ратификацию.
Предположим, что какой-нибудь другой процесс $Q$, который начал следующий раунд не с предпочтением $v$.
Чтобы это произошло, $Q$ должен был не получить ни одной ратификации, то есть получить $N-f$ сообщений вида $(2, k, ?)$.
Но тогда всего в системе было $(f+1)+N-f=N+1>N$ сообщений, противоречие.

Таким образом, если когда-то решение и приняли, то в следующем раунде у нас предпочтение у всех процессов равно этому решению, после чего
им остаётся только проголосовать за него, единогласно ратифицировать и решить.

=== Остановка алгоритма ===
Когда какой-нибудь процесс принимает решение, он может разослать всем остальным сообщение "Решение принято" и остановиться.
Это сообщение дойдёт до всех живых процессов за конечное время, после чего они тоже остановятся.
То, что они будут пытаться достучаться до остановившихся процессов или общаться между собой, нам неважно.

=== Оценки ===
Без доказательства.
Но у нас есть недетерминированный алгоритм в асинхронной системе с сильным противником с вероятностью завершения за конечное число шагов, равной единице.
Правда, среднее время работы экспоненциально: $O(2^N)$, потому что нам надо, чтобы случайными флуктуациями получилось достаточно много одинаковых битов.
Примерная причина: мы хотим случайно получить ситуацию, в которой есть больше $\frac N 2$ одинаковых битов из каких-то $N - f$, которые нам подсунул противник).

Алгоритм не очень практичный, но интересный: показывает, как использовать монетку.

Теорема Фишера-Линча-Патерсона (FLP)

2019-06-04T05:49:43Z

Yeputons:

[[Категория:Параллельное программирование]]
Теорема Фишера, Линча и Патерсона (FLP, 1985 год): невозможно достичь даже необоснованного [[Консенсус в распределённой системе|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:
* Алгоритм должен завершиться за конечное время.
* Один из узлов [[Иерархия ошибок в распределённых системах|может отказать]]
* Система [[Асинхронные и синхронные распределённые системы|асинхронна]]
* Алгоритм должен быть детерминирован.

Если разрешаем незавершаемость в случае отказов, есть [[Paxos]] и [[Raft]].
Если отказов нет, есть [[Консенсус в распределённой системе#Решение при отсутствии отказов|простой алгоритм]].
Если система синхронна, то есть [[консенсус в синхронных системах]].
Если разрешаем недетерминизм, то есть [[алгоритм Бен-Ора]].

При этом даже если разрешить одновременную посылку сообщения сразу нескольким процессам (как в [[Общий порядок сообщений|общем порядке сообщений]]) и тем самым запретить процессу падать при массовой рассылке сообщений, лучше не станет: нет гарантии, в каком порядке и как скоро эти сообщения будут получены и обработаны получателями.
А вот если какую-нибудь гарантию дадим, то получаем [[Переформулировки консенсуса в распределённой системе#Terminating Reliable Broadcast (TRB)|TLB]], из которого сразу выводится консенсус.

== Доказательство ==
Из презентации Р. Елизарова.

От противного: пусть есть такой алгоритм, тогда мы проанализируем варианты его исполнения, подстроим порядок доставки сообщений (без откладывания сообщений бесконечно далеко), получим бесконечную цепочку выполнения и противоречие с конечностью алгоритма.

=== Модель ===
{{Определение
|definition=
'''Процесс''' — это детерминированный автомат, который может выполнять три операции:
* <code>receive() : msg</code> — бесконечная блокировка до получения ближайшего сообщения. Так как система асинхронна, возможности "посмотреть следующее сообщение" или ''таймаутов нет''.
* <code>send(msg)</code> — отправка сообщения другому процессу. Гарантируется, что сообщение дойдёт получателю за конечное время, но это время может быть сколь угодно большим.
* <code>decided(value)</code> — процесс принял решение <code>value</code>. Решение процесс может принять только один раз, но после этого он ''может продолжить выполняться'' и помогать остальным процессам.
Заметим, что так как нет "времени", можно считать все переходы в процессе мгновенными.
}}
Для доказательства от противного у нас есть такой алгоритм для процессов, что все они вызывают <code>decided(value)</code> с одинаковым значением через конечное время, независимо от того, как система задерживает сообщения.
{{Определение
|definition=
'''Конфигурация''' — это состояния всех процессов плюс все сообщения в пути (которые отправили, но ещё не доставили).
}}
В начальной конфигурация у каждого процесса может быть сколько угодно входных данных и даже своя программа.
Начальных конфигураций может быть несколько, они могут отличаться, например, предложениями процессов.
{{Определение
|definition=
'''Шаг''' из одной конфигурации в другую — это приём какого-то сообщения процессом (событие) и последовавшие за этим внутренние действия процесса до следующего <code>receive()</code>. Эти действия ''однозначно'' определяются предыдущей конфигурацией и событием.
}}
{{Определение
|definition=
'''Исполнение''' — это ''бесконечная'' цепочка шагов из какой-нибудь начальной конфигурации. Бесконечная, потому что процессы могут выполняться и после принятия решений.
}}
{{Определение
|definition=
'''Отказавший процесс''' — это процесс, который делает только конечное количество шагов в исполнении. Такой в системе может быть максимум один (это более сильное условие, чем если может много процессов отказывать).
}}

Также гарантируется, что в любом исполнении любое сообщение, предназначенное не отказавшему процессу, обрабатывается через конечное число шагов.
Другими словами, ''сообщения не теряются''.

=== Валентность ===
Заметим, что в любом исполнении всегда принимается решение.
Даже если один процесс отказал, то все остальные должны прийти к решению за конечное число шагов.
{{Определение
|definition=
Конфигурация называется '''$i$-валентной''' и '''одновалентной''', если все цепочки шагов из неё приводят к решению $i$.
Таким образом, бывают 0-валентные и 1-валентные конфигурации.
Если же из конфигурации есть цепочки, приводящие к каждому из решений, то такая конфигурация называется '''бивалентной'''.
}}
'''Наблюдение''': пусть из конфигурации $X$ есть цепочка шагов, обрабатывающая сообщения из $X$ в подмножестве процессов $A$, за которой идёт цепочка процессов, обрабатывающая сообщения из $X$ в подмножестве процессов $B$, и в конце мы получили конфигурацию $Y$. Тогда эти цепочки коммутируют: можно сначала обработать сообщения подмножеством процессов $B$, а потом — $A$ (так как мы обрабатываем только сообщения из $X$, а не новые).

'''Наблюдение''': за $i$-валентной конфигурацией могут следовать только $i$-валентные.

=== Начальная бивалентная конфигурация ===
'''Лемма''': существует бивалентная начальная конфигурация.

Доказательство от противного: пусть все начальные конфигурации одновалентны.
Из нетривиальности консенсуса мы знаем, что есть как 0-, так и 1-валентные начальные конфигурации.
Тогда можно найти две начальные конфигурации разной валентности, которые отличаются только состоянием одного процесса:
взяли две произвольные начальные конфигурации разной валентности, начали переводить одну в другую копированием исходных состояний процессов, по одному процессу за шаг.

А раз есть две такие конфигурации разной валентности, то пусть в каждой из них этот процесс (где они отличаются) откажет с самого начала, до отправки и приёма любых сообщений.
Тогда мы всё ещё получим консенсус, но решение будет одинаковым, потому что внешняя система никак не может выявить состояние отказавшего процесса.
А они исходно были разной валентности, противоречие.

=== Цепочка бивалентных конфигураций ===
'''Лемма''': для любой бивалентной конфигурации можно найти следующую за ней бивалентную.

'''Следствие''': если лемма верна, то мы можем построить бесконечную цепочку бивалентных конфигураций и тем самым получим противоречие и докажем FLP: есть бесконечная цепочка, в которой не принято решение.

'''Доказательство''': от противного.
Пусть все конфигурации после некотороый бивалентной конфигурации $G$ одновалентны.
Введём определения:
* $e$ — какое-то событие в $G$, скармливающее сообщение $m$ процессу $p$. Такое есть, иначе у нас в конфигурации ничего не происходит, она бивалентна, а решение должно быть детерминированным, противоречие.
* $C$ — множество конфигураций, достижимых из $G$ без использования $e$. В частности, в $C$ по предположению отсутствуют бивалентные конфигурации.
* $D=e(C)$, то есть все конфигурации, достижимые из $G$, где $e$ — последнее обработанное событие. В частности, в $D$ по предположению отсутствуют бивалентные конфигурации.
Теперь докажем, что $D$ содержит бивалентную конфигурацию.
То есть мы выбрали, насколько сильно отложить обработку произвольного события $e$ и показали, что это не порушит бивалентность.
Надо ещё аккуратно, чтобы это не порушило конечность обработки каждого сообщения.
Например, их можно обрабатывать по очереди, начиная с самых старых.
Тогда каждое событие рано или поздно попадёт в наш шаг и будет обработано.

[[Файл:distributed-flp-proof-cd.png|500px]]

==== Шаг 1: существование $i$-валентных конфигураций в $D$ ====
'''Подлемма''': для любого $i$ в $D$ существует $i$-валентная конфигурация.

В самом деле: так как $G$ бивалентна, то по какой-то цепочке шагов из неё можно дойти до $i$-валентной конфигурации $E_i$.
Дальше разбором случаев находим искомую конфигурацию в $D$:
* Если $E_i \in D$, то мы доказали подлемму.
* Если $E_i \in C$, то $e(E_i) \in D$, у $e(E_i)$ такая же валентность и мы снова доказали подлемму.
* Иначе ребро $e$ применялось в цепочке шагов для достижения $E_i$ из $G$. Найдём конфигурацию $F_i \in D$, которая была в этой цепочке шагов сразу после применения $e$. Так как в $D$ нет бивалентных конфигураций, то $F_i$ является $i$-валентной, что и требовалось.

==== Шаг 2: существование соседних разновалентных конфигураций ====

Теперь мы хотим найти такие две соседние конфигурации $C_0, C_1 \in C$ (отличающиеся переходом $e'(C_0)=C_1$), что $D_0=e(C_0) \in D$ является 0-валентной, а $D_1=e(C_1)$ — 1-валентной (или наоборот).
Это можно сделать, если взять в $D$ конфигурацию $e(C_1)$, отличающуюся от валентности $e(G)$, а дальше посмотреть на цепочку конфигураций между $G$ и $e(C_1)$ и найти момент смены валентности.

Начнём искать, более строго. Не теряя общности можем сказать, что $e(G)\in D$ является 0-валентной (иначе повторим доказательство шага).
По предыдущему шагу найдём в $D$ 1-валентную конфигурацию $D_1=e(C_1)\in D$.
Конфигурация $C_1$ получена какой-то конечной непустой цепочкой сообщений $x_1, x_2, \dots, x_k$.
Будем по очереди убирать по одному сообщения с конца и смотреть на валентность конфигураций $e(x_{k-1}(\dots(x_1(G))\dots))$, $e(x_{k-2}(\dots(x_1(G))\dots))$, \dots — в какой-то момент она сменится с единицы на ноль (например, при пустой цепочке, т.е. при рассмотрении $e(G)\in D$).
Тогда мы как раз нашли искомую пару соседей $C_0$ и $C_1$ таких, что $e(C_0)$ и $e(C_1)$ разной валентности.

==== Шаг 3: разбор случаев ====
Теперь у нас, помимо конфигурации $C$ и события $e$, есть некоторое событие $e'$ и конфигурации $C_0$ и $C_1$, причём:
* $e(C_0)=D_0$ является 0-валентной, а $e(C_1)=D_1$ является 1-валентной (или наоборот, повторим доказательство)
* $e'(C_0)=C_1$

Разберём два случая, в зависимости от того, одному процессу приходят $e$ и $e'$ или разным.

===== Разным =====
Пусть $proc(e)\neq proc(e')$ (т.е. эти события в разных процессах).
Тогда нам всё равно, в каком порядке их обрабатывать, т.е. $e'(e(C_0))=e(e'(C_0))=e(C_1)=D_1$:

[[Файл:Distributed-flp-proof-case1.png|300px]]

Мы знаем, что $D_1$ является 1-валентной. Но так как они достижима из $D_0$, то она также является и 0-валентной, противоречие.

===== Одному =====
Пусть $proc(e) = proc(e') = p$ (т.е. это два сообщения одному и тому же процессу).
Тогда рассмотрим цепочку шагов $\sigma$ от состояния $C_0$, в которой процесс $p$ вообще отказал вместо обработки сообщений.
Тогда остальные процессы в этой цепочке пришли к какому-то решению в конфигурации $A=\sigma(C_0)$.
Тогда эта конфигурация должна быть либо 0-, либо 1-валентной (в ней уже принято решение).

[[Файл:Distributed-flp-proof-case2.png|400px]]

Но теперь мы можем сказать, что процесс $p$ не отказал, а просто очень долго работал и теперь получает событие $e$.
Так как $\sigma$ не обращается к $p$, то $E_0=e(\sigma(C_0)=\sigma(e(C_0))=\sigma(D_0)$ — конфигурация, достижимая из 0-валентной, т.е. тоже 0-валентная.

С другой стороны, можно аналогично сказать, что процесс $p$ теперь получает сообщение $e'$, а за ним — сообщение $e$.
Тогда получается $E_1=e(e'(\sigma(C_0))$.
Из-за коммутативности получаем $E_1=\sigma(e(e'(C_0)))=\sigma(e(C_1))=\sigma(D_1)$ — конфигурация, достижимая из 1-валентной, т.е. тоже 1-валентная.

Таким образом получаем, что из $A$ достижимы и 0-валентная, и 1-валентная конфигурация, противоречие.

== Ссылки ==
* http://bailonga.es/tpmtp/lecture09.pdf
* https://github.com/volhovm/study-notes/blob/master/parallel_programming/parallel_programming.org

Параллельное программирование

2019-06-04T05:34:32Z

Yeputons: /* 6 семестр */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
*[[Базовые определения и формализм]]
*[[Алгоритмы взаимного исключения]]
*[[Стек Трайбера]]
*[[Формализм распределённых систем]]

==6 семестр==
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===1-2 билеты. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран)

===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат (WCP)]]
*[[Централизованный алгоритм для WCP]]
*[[Распределенный алгоритм для WCP]]

===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
* [[Диффундирующие вычисления]]
* [[Алгоритм Дейкстры и Шолтена]]

===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]
*[[Определение взаимной блокировки]]

===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
* [[Иерархия порядков сообщений]]
* [[Алгоритм для FIFO порядка]]
* [[Алгоритм для причинно-согласованного порядка]]
* [[Алгоритм для синхронного порядка]]

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

===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===

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

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

===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Консенсус в синхронных системах]]

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

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

=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Алгоритм Бен-Ора]]

=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
* [[Replicated State Machine]]
* [[Paxos]]

=== 30 билет. Raft. Алгоритм, его свойства.===
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
* [[Транзакции в распределённых системах]]
* [[2 Phase Locking]]

=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
* [[Транзакции в распределённых системах]]
* [[2 Phase Commit]]

=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
* [[CAP теорема]]

=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
* [[Gossip-протоколы]]
* [[CRDT]]

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

==Ссылки==
<references/>

Параллельное программирование

2019-06-04T05:33:54Z

Yeputons: /* 28 билет. Paxos. Алгоритм, его свойства. */

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
*[[Базовые определения и формализм]]
*[[Алгоритмы взаимного исключения]]
*[[Стек Трайбера]]
*[[Формализм распределённых систем]]

==6 семестр==
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===1-2 билеты. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран)

===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

===8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

===11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя===

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

===13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат (WCP)]]
*[[Централизованный алгоритм для WCP]]
*[[Распределенный алгоритм для WCP]]

===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
* [[Диффундирующие вычисления]]
* [[Алгоритм Дейкстры и Шолтена]]

===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]
*[[Определение взаимной блокировки]]

===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
* [[Иерархия порядков сообщений]]
* [[Алгоритм для FIFO порядка]]
* [[Алгоритм для причинно-согласованного порядка]]
* [[Алгоритм для синхронного порядка]]

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

===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===

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

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

===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===

* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Консенсус в синхронных системах]]

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

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

=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Алгоритм Бен-Ора]]

=== 28 билет. Paxos. Алгоритм, его свойства.===
* [[Replicated State Machine]]
* [[Paxos]] (гарантии)

=== 29 билет. Paxos. Общие принципы. Основные модификации.===
=== 30 билет. Raft. Алгоритм, его свойства.===
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
* [[Транзакции в распределённых системах]]
* [[2 Phase Locking]]

=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
* [[Транзакции в распределённых системах]]
* [[2 Phase Commit]]

=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
* [[CAP теорема]]

=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
* [[Gossip-протоколы]]
* [[CRDT]]

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

==Ссылки==
<references/>

Асинхронные и синхронные распределённые системы

2019-06-04T05:33:18Z

Yeputons:

[[Категория:Параллельное программирование]]
* Синхронные системы
** Известно, что любое сообщение либо доставляется за некоторое время $C$, либо полностью исчезает
** Тогда можно разбить выполнение алгоритма на фазы длиной $O(C)$: в начале фазы все процессы отправляют сообщения, потом ждут, а в конце знают, что получили все сообщения, которые только могли прийти
* Асинхронные системы
** Время передачи сообщения сверху не ограничено
** Но гарантируется, что если нет отказов, то сообщение рано или поздно дойдёт
** Мы принципиально не можем использовать таймауты, поэтому нельзя смотреть на время даже внутри одного процесса: он либо что-то делает внутри себя, либо ждёт очередного сообщения бесконечно долго.

Асинхронную систему можно на практике попробовать(?) превратить в синхронную при помощи таймаутов: к каждому сообщению прикрепляем wall clock time (которое не может быть идеально синхронизировано в распределённой системе, но на практике хоть как-то можно, сбои не всегда играют против нас) и игнорируем слишком старые сообщения. Надо аккуратно поиграть с определениями и учесть погрешность и потребовать, чтобы часы не расходились, возможно, ещё что-то.
Выберем большой таймаут — будет тормозить, выберем маленький — будут большие потери сообщений.

Если решили задачу для асинхронной системы, то в синхронной будет работать то же самое.
Но, возможно, для синхронной системы существует более эффективный или простой алгоритм.
Обратное тоже возможно: например, пока синхронная система будет ждать таймаута, асинхронная может быстро забить дожидаться ответа и всё сделать.

На практике могут использоваться алгоритмы и для тех, и для других.

2 Phase Commit

2019-06-03T21:15:00Z

Yeputons:

[[Категория: Параллельное программирование]]
'''Алгоритм двухфазного коммита''' — классический централизованный оптимистичный алгоритм распределённого консенсуса из баз данных для подтверждения [[Транзакции в распределённых системах|распределённых транзакций]].

После того, как мы завершили транзакцию, её надо атомарно подтвердить на всех участниках (participants).
У каждой транзакции есть выделенный координатор (transaction coordinator).
Алгоритм работает в две фазы:

# '''Запрос (request)''': координатор спрашивает каждого участника: "готов ли ты ''очень быстро и гарантированно'' завершить транзакцию?". Если кто-нибудь ответил "нет", то отменяем транзакцию. Если кто-то отвечает "да", то он должен уметь обеспечить завершение транзакции даже если упадёт и поднимается (например, все данные уже в журнале).
# '''Завершение''': координатор принимает решение о закреплении (commit) или отмене (rollback) транзакции и записывает его в свою надёжную память, после чего рассылает всем решение. После рассылки можно сообщить о фиксации транзакции, подтверждения от участников ждать не нужно (но тогда может быть проблема с тем, что следующие чтения из СУБД будут возвращать старые данные, пока не закоммитили).

При этом проблемы двух генералов на практике обычно нет: после того, как координатор принял решение о транзакции, он будет его доносить до всех любопытствующих узлов.

Всего на коммит требуется $3N$ сообщений ($N$ — количество участников транзакции) и задержка порядка $3\cdot RTT$ (round-trip time).

== Ограничения ==
Так как это алгоритм консенсуса, к нему применима [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]].

Если у нас есть отказы узлов или связи, то 2PC будет ждать, пока связь не восстановится:
* Если отказ произошёл на первой фазе, то координатор может отменить транзакцию по таймауту.
* После того, как координатор перешёл на вторую фазу, он не имеет права успокоиться, пока не донесёт своё решение до всех узлов.
* Если узел отказал, а потом восстановился, то он спрашивает координатора, какое решение было принято. Если "да", то обязан закрепить транзакцию (т.е. координатор должен хранить все подтверждённые транзакции, которые подтвердили не все узлы).
* Если отказал координатор, то, если узел ответил "да", он не имеет права забить на транзакцию, пока координатор не восстановится.

Но алгоритм классический, простой, на практике неплохо работает, потому что сложно только с отказами координатора и отказами узлов на второй фазе (когда решение о коммите уже принято), а такое бывает не так часто.

Алгоритм Лампорта-Шостака-Пиза

2019-06-03T21:14:04Z

Yeputons: /* N=4, f=1 с лекции */

[[Категория:Параллельное программирование]]
Алгоритм Лампорта-Шостака-Пиза (1982) решает [[Проблема византийских генералов|проблему византийских генералов]]: если имеется $N$ процессов, среди которых не более $f$ византийских, причём $3f < N$, то они могут прийти к консенсусу за конечное время, используя надёжные каналы связи.

== N=4, f=1 с лекции ==
В первой фазе все процессы шлют своё предложение всем остальным, во второй — пересылают все полученную информацию всем остальным, итого $2N^2$ сообщений.

У каждого невизантийского процесса появляется матрица информации: кто кому что сказал.
Рассмотрим пример такой матрицы (процесс не знает, какой процесс византийский, мы пометили для демонстрации):

[[Файл:distributed-byzantine-4-1.png|600px]]

Диагональ вычёркиваем, нам эту информацию и так дали на первой фазе и ей нельзя верить в любом случае (например, так мы вычёркиваем $t_7$, что важно для доказательства ниже).

В столбце византийского процесса находится что угодно, потому что он мог нам сказать что угодно (то есть $t_4$, $t_5$ и $t_6$ могут быть разные у всех процессов).
В строчке византийского процесса тоже находится что угодно, но одинаковое для всех процессов, потому что
содержимое этой строчки нам гарантированно рассказывают честные процессы (т.е. $t_1$, $t_2$ и $t_3$ одинаковые для всех процессов).
Так что большинство в строчке византийского процесса ($t$) непонятное, но одно для всех честных процессов.

А в строчках нормальных процессов находятся константы, за исключением одного столбца от византийского процесса.
Таким образом, большинство в каждой строчке (кроме одной византийской) — это то, что соответствующий процесс реально рассылал ($x$, $y$, $z$).

Следовательно, теперь у всех нормальных процессов множество из большинств по строкам одинаковое.
Можно применять детерминированную функцию для выбора консенсуса.
То есть византийский процесс не может помешать достигнуть консенсуса, но иногда может его изменить.

== Идея общего случая с $f>1$ ==
Надо сделать ещё несколько стадий.
На первой рассылаем значения, на второй — матрицы, на третьей — кубики (мне прислали такую матрицу), и так далее.
На экзамене подробнее не требуется.

Впрочем, описание в Garg (секция 15.4.2, страница 244) требует $N > 4f$, а не $N > 3f$.

== Общий случай из старых конспектов ==
Считаем, что у процессов есть номера. Процесс 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.

Консенсус в распределённой системе

2019-06-03T21:13:35Z

Yeputons: /* Решение при отсутствии отказов */

[[Категория:Параллельное программирование]]
{{Определение
|definition=
'''Задача консенсуса''': есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
* Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать.
* Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям (возможно, просто с разными исходными предложениями или разным исходным состоянием процессов).
}}
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.

Предложение/решение может быть битом, числом, чем-нибудь ещё — это всё друг к другу сводится.
Доказательств не было, они очень технические, есть в толстенной книжке Линча.
Но нужно примерно понимание, как сводить консенсус на бите к консенсусу на чём-нибудь сложном.

Можно ещё требовать '''обоснованный''' консенсус: это когда принятое решение должно совпадать с одним из исходных предложений.
Необоснованный консенсус к обоснованному тоже сводится: сначала выбираем лидера (см. ниже), а потом лидер делает обоснованный выбор
(если возникают потери сообщений или падения, то всё тухло).
Формальное доказательство, опять же, опущено.

== Решение при отсутствии отказов ==

Каждый процесс рассылает всем остальным своё предложение.
Каждый процесс ждёт предложения остальных, после чего детерминированной функцией выбирает элемент из множества.
У остальных процессов получилось такое же множество, такая же функция, следовательно, такой же результат.
Работает даже в асинхронной системе, $N^2$ сообщений.

Алгоритм Скина

2019-06-03T21:13:17Z

Yeputons:

[[Категория: Параллельное программирование]]
'''Алгоритм Скина'''<ref>https://doi.org/10.1109/TSE.1983.236608</ref> для организации [[Общий порядок сообщений|общего порядка сообщений]].
Лучше, чем [[Алгоритм Лампорта]], потому что для multicast сообщений общается только с получателями, а не со всеми процессами системы.

Используются [[Логические часы Лампорта|логические часы Лампорта]].
Ниже алгоритм расписан чуть подробнее, чем в Garg и на лекции, но вроде всё ещё верно.

У каждого процесса есть очередь принятых необработанных multicast сообщений.
Каждое сообщение имеет временну́ю метку и флаг — финализирована ли метка.

# Инициатор отправляет сообщение и своё время (''предварительное время сообщения'') всем получателям
# При приеме сообщения процесс запоминает сообщение со временем в очередь (как нефинализированное) и отправляет свое время инициатору
# Когда инициатору вернулись все подтверждения, он выбирает максимальное время из них и снова отправляет сообщение со финализированным временем
# Получатель может обработать сообщение, если оно помечено как финальное и имеет минимальное время среди всех известных получателю сообщений (и финальных, и нефинальных; иначе может получиться, что финализация сообщений произойдёт в разном порядке у разных получателей и нарушится общий порядок)

Полный порядок задается финальными временными метками. Финальные метки нужны, чтобы как-то зависеть от времени получателей.
Доказательство на лекции и в Gaarg не приводилось.

Итого $3(k-1)$ сообщений на каждый multicast на $k$ процессов (не обсуждалось на лекции, но вроде так).

Алгоритм для синхронного порядка

2019-06-03T21:12:24Z

Yeputons:

[[Категория: Параллельное программирование]]
Этот алгоритм берёт систему с асинхронным(?) порядком и начинает гарантировать в ней [[Иерархия порядков сообщений#Синхронный порядок|синхронный порядок]].

Алгоритм для синхронного порядка основан на иерархии процессов (точнее, произвольном DAG процессов, отправлять сообщения могут только соединённые ребром), мы рассмотрим полный линейный порядок.
Упорядочим процессы по номеру, назовем сообщение ''большим'', если номер отправителя больше номера получателя, и ''малым'' иначе.
Процесс может быть в ''активном'' или ''пассивном состоянии''. Изначально все активны.
В пассивном состоянии процесс не может ни отправлять, ни получать сообщения, он их складывает в очередь и ждёт, пока не станет активным.

Если процесс хочет отправить большое сообщение, то он его отправляет и ждёт подтверждения.
А пока ждёт — становится пассивным.

[[Файл:distributed-order-sync-algo-big.png|400px]]

Чтобы отправить сообщение большему процессу <tex>P_j</tex>, процесс <tex>P_i</tex> сначала посылает служебное сообщение, ''запрос''. В ответ <tex>P_j</tex> отправляет ''разрешение''; он может сделать это только в активном состоянии. Разрешив, он становится пассивным и остается в этом состоянии, пока не получает сообщение, которое разрешил.

[[Файл:distributed-order-sync-algo-small.png|400px]]

Таким образом, сообщения по факту "передаются" только от больших к маленьким и тогда можно нарисовать стрелочки.
Взаимная блокировка наступить не может: мы ждём только меньших процессов, а транзитивность у нас есть и циклов быть не может.
Если маленький хочет отправить сообщение большому, то он отсылает запрос и продолжает работать (посылать большие и маленькие сообщения, менять своё состояние).
Ничего страшного, что по факту сообщение "отправится" только через какое-то время — с точки зрения процесса оно просто долго было в пути.

Разумеется, надо аккуратно доказать, что функцию $T$ можно придумать. Это делается на странице 200 в Gaarg, там происходит что-то вроде логических часов.

Итого на $m$ сообщений нам требуется послать не больше $3m$ сообщений (худший случай — все сообщения маленькие).

Барьерная синхронизация (3 алгоритма)

2019-06-03T21:10:53Z

Yeputons: /* Алгоритмы */

[[Категория: Параллельное программирование]]
== Определение и полезность ==
{{Определение
|definition=
Интервал <tex>[G, H]</tex> (<tex>G \subseteq H</tex>) называется '''барьерно-синхронизированным''', если для любых событий <tex>e \in G</tex> и <tex>f \notin H</tex> верно, что $e \rightarrow f$.
}}
Другими словами, все события слева от интервала произошло до всех событий справа от интервала.
Это сильнее [[Согласованный интервал|согласованных интервалов]]: те требуют лишь отсутствия стрелок справа налево (коих в барьере не может быть, потому что есть вообще все возможные стрелки слева направо, а в две стороны стрелки не бывает).

Как следствие, внутри любого барьерно-сихнронизированного интервала тоже есть согласованный срез (где-то, не знаем, где).
А искать такой интервал намного проще, чем [[Алгоритм Чанди-Лампорта|искать согласованный срез]] и по коду, и по количеству сообщений (линия вместо квадрата).

== Алгоритмы ==

*[[Централизованный]]: все посылают токен координатору, затем он посылает всем. <tex>2N</tex> сообщений, низкая задержка;
* Каждый посылает каждому токен. <tex>N^2</tex> сообщений, низкая задержка;
* Token по кольцу два раза, <tex>2N-1</tex> сообщение, высокая задержка (вроде можно $2N-2$ сообщений).
[[Файл:Token_ring.png|200px|thumb|left]]

Барьерная синхронизация (3 алгоритма)

2019-06-03T21:09:47Z

Yeputons: /* Алгоритмы */

[[Категория: Параллельное программирование]]
== Определение и полезность ==
{{Определение
|definition=
Интервал <tex>[G, H]</tex> (<tex>G \subseteq H</tex>) называется '''барьерно-синхронизированным''', если для любых событий <tex>e \in G</tex> и <tex>f \notin H</tex> верно, что $e \rightarrow f$.
}}
Другими словами, все события слева от интервала произошло до всех событий справа от интервала.
Это сильнее [[Согласованный интервал|согласованных интервалов]]: те требуют лишь отсутствия стрелок справа налево (коих в барьере не может быть, потому что есть вообще все возможные стрелки слева направо, а в две стороны стрелки не бывает).

Как следствие, внутри любого барьерно-сихнронизированного интервала тоже есть согласованный срез (где-то, не знаем, где).
А искать такой интервал намного проще, чем [[Алгоритм Чанди-Лампорта|искать согласованный срез]] и по коду, и по количеству сообщений (линия вместо квадрата).

== Алгоритмы ==

*[[Централизованный]]: все посылают токен координатору, затем он посылает всем. <tex>2N</tex> сообщений, низкая задержка;
* Каждый посылает каждому токен. <tex>N^2</tex> сообщений, низкая задержка;
* Token по кольцу два раза, <tex>2N</tex> сообщений, высокая задержка.
[[Файл:Token_ring.png|200px|thumb|left]]

Алгоритм Дейкстры и Шолтена

2019-06-03T21:09:19Z

Yeputons:

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

Основная идея: выстроить процессы в дерево: кто кого активизировал. Процесс добавляется в дерево (становится "красным"), когда становится активным, а удаляется (становится "зелёным"), когда он и все его потомки стали пассивными и там нет сообщений (т.е. поддерево закончило вычисления). Исходно дерево содержит только инициатора, а когда вычисление остановится, станет пустым (о чём узнает инициатор).

Каждый процесс будет требовать подтверждения на каждое своё сообщение, чтобы можно было учесть сообщения в пути.

Каждый процесс хранит внутри себя несколько чисел:
# Количество неподтверждённых сообщений остальным процессам. Увеличивается при отправке сообщения, кроме ack. Уменьшается при получении ack (у нас всё ещё не бывает ошибок и перепосылок, они дальше в билетах).
# Количество детей в дереве.
# Номер родительского процесса (null для инициатора, он же корень).

Процесс называется ''зелёным'', если выполняются все следующие условия:
# Процесс пассивен (в смысле диффундирующего вычисления, в нашем алгоритме он всё ещё может общаться с остальными)
# Нет неподтверждённых сообщений другим процессам
# У него нет детей в дереве

В противном случае процесс называется ''красным''.
Дерево состоит в точности из множества красных процессов.
Чтобы поддерживать этот инвариант, требуется задать поведение процессов:
* Зелёный процесс не отправляет никому сообщения
* Зелёный процесс остаётся зелёным, пока не получит сообщение (это не может быть ack, и это сообщение только от красного):
** При получении становится красным и новым листом в дереве
** Отсылает автору сообщения сообщения "я твой новый ребёнок", после чего автор увеличивает количество своих детей
* Красный процесс может отправить сообщение другому красному, тогда никаких изменений состояния не происходит (только меняется счётчик неподтверждённых сообщений у отправителя)
* Красный процесс остаётся красным, пока не начинают выполняться условия для становления зелёным:
** Если процесс стал зелёным, он удаляет себя из дерева, послав родителю сообщения "я больше не твой ребёнок", после чего родитель уменьшает количество своих детей

Тогда диффундирующее вычисление заканчивается в точности когда корень дерева (инициатор) становится зелёным.

Итого у нас получается $N$ процессов и $m$ сообщений в сумме требуется послать $2m+k\le 3m$ сообщений(?), где $k$ — количество раз, которые вершина становится красной:
* На каждое из $m$ сообщение идёт ответ: либо с пометкой "я твой новый ребёнок", либо без пометки.
* Каждый раз, когда вершина становится красной, она должна в какой-то момент стать обратно зелёной и отправить родителю оповещение.

Алгоритм Рикарта-Агравалы

2019-06-03T21:04:43Z

Yeputons:

[[Категория: Параллельное программирование]]
'''Алгоритм Рикарта-Агравалы''' — алгоритм взаимного исключения, являющийся оптимизацией [[Алгоритм Лампорта взаимного исключения|алгоритма Лампорта]].

Мы объединяем запросы rel и ok в один: вместо отправки ok сразу посылаем только если не хотим входить в критическую секцию или сразу как только выйдем из секции.

# Когда процесс <tex>P_i</tex> хочет войти в критический участок, то рассылает всем сообщение req с текущей временной меткой.
# Когда процесс <tex>P_k</tex> получает от <tex>P_j</tex> запрос войти в критический участок:
#* если он сам не посылал запрос, то посылает отклик;
#* если он послал свой запрос, он сравнивает временные метки этих двух запросов и посылает отклик только если у его собственного запроса метка позже (на самом деле, при равенстве меток, нужно проверять, у кого больше номер, т.е. для отсутствия блокировок нужно ввести приоритет на потоках);
#* в остальных случаях процесс <tex>P_k</tex> задерживает отправку отклика.
# Процесс может войти в критический участок только после получения откликов ото всех других узлов сети.
# После выхода из него он рассылает задержанные отклики на все ожидающие запросы.

В отличие от алгоритма Лапрота, нам не требуется ни третьего сообщения, ни хранить очередь запросов в каждом процессе.

[[Файл:mutex-distributed-ricart.png|400px]]

Алгоритм является starvation-free. Суммарно на каждую критическую секцию приходится <tex>2 \cdot (N-1)</tex> сообщений.

Отказ любого узла приводит к зависанию. Решается проблема введением таймаутов.

Самостабилизирующиеся алгоритмы

2019-06-03T21:02:37Z

Yeputons:

[[Категория: Параллельное программирование]]
{{Определение
|definition=
'''Самостабилизирующие алгоритмы''' — это идея построения алгоритмов, устойчивых к ошибкам:
* Код потерять сложно, поэтому мы считаем, что он не портится при падении узлов.
* Алгоритм может работать с любой комбинацией данных.
* Из любого состояния мы попадаем в '''легальное''' через конечное число шагов (при отсутствии сбоев).
}}
Тогда от ''любого'' сбоя мы через конечное число шагов будем восстанавливаться без консенсусов и прочих развлечений.
== Взаимное исключение ==
Dijkstra Stabilizing Token Ring Algorithm.

Сначала надо переформулировать задачу: мы говорим, что каждый процесс в системе может либо '''иметь привилегию''', либо не иметь.
В произвольном состоянии системы привилегия может быть у произвольного количества процессов, но через конечное число шагов она остаётся только у одного процесса и мы входим в легальное состояние.
Дальше остаёмся только в легальных состояниях.

TODO: а какие сообщения процессы посылают друг другу? Могут ли быть ошибки (наверное, нет)? Может ли система быть асинхронной (наверное, тоже нет)?

Все $N$ процессов будут замкнуты в кольцо, в котором один процесс назван "первым".
У каждого процесса есть состояние — число от 0 до $K-1$, причём $K \ge N$ — параметр алгоритма.

По определению положим, что у процесса есть привилегия, если:
* Он первый и его значение $S$ совпадает со значением $L$ следующего по часовой стрелке процесса.
* Он не первый и его $S$ не совпадает с $L$.

Например, на рисунке ниже толстая граница у выделенного процесса, а жёлтым обозначена привилегия:

[[Файл:distributed-self-stabilization-legal.png|400px]]

Правила перехода в новое состояние:
* Для первого процесса: если была привилегия ($S=L$), то переходим в состояние $(S + 1) \bmod K$
* Для не-первого процесса: если привилегия есть ($S \neq L$), то переходим в состояние $
Пример двух переходов:

[[Файл:Distributed-self-stabilization-step-1.png|400px]]

[[Файл:Distributed-self-stabilization-step-2.png|400px]]

Таким образом, в легальном состоянии привилегия у нас ходит по кругу, как в алгоритме с токеном.
Но там потеря токена была смертельной для алгоритма, а у нас — не смертельна.

=== Доказательство стабилизируемости ===
'''Лемма''': в любом состоянии хотя бы у одного процесса есть привилегия.
В противном случае у нас, с одной стороны, все значения машин равны друг другу (потому что для каждой машины, кроме первой, её значение совпадает со следующей по кругу), а с другой стороны значение первой машины и её соседа должны отличаться, противоречие.

'''Лемма''': что бы не происходило в системе, через $O(N^2)$ шагов в системе первый процесс сделает ход.
'''Доказательство (с лекции)''': если первый процесс не делает ход, то следующий за ним против часовой стрелки процесс 2 сможет сделать максимум один ход: взять себе значение первого процесса.
Процесс 3 после каждого хода процесса 2 может сделать максимум один ход: взять себе значение процесса 2.
То есть процесс 3 может сделать не больше двух ходов (один исходно, один после хода процесса 2).
Аналогично, процесс 4 может сделать не больше трёх ходов, и так далее.
Итого мы получаем, что если первый процесс не делает шаги, то через $O(N^2)$ шагов привилегия полностью исчезнет, чего не бывает.

'''Альтернативное доказательство (проверено рандомом)''': если первый процесс может сделать ход сразу, то всё доказали.
Иначе у него нет привилегии.
Заметим, что если следующий за ним по часовой стрелке процесс 2 либо имеет значение, равное ему, либо отличающееся (тогда он имеет привилегию и сразу делает ход).
Таким образом, через один ход процессы 1 и 2 имеют одинаковые значения.
Аналогично, через два хода процессы 1, 2 и 3 имеют одинаковые значения.
А через $N-1$ шаг все процессы гарантированно имеют одинаковые значения (если первый процесс так и не походил).
Таким образом, через $N-1$ шаг у первого процесса появляется привилегия и он ходит, $N=O(N^2)$.

'''Лемма''': рано или поздно у первого процесса будет уникальное $S$.
'''Доказательство''': все остальные процессы умеют только копировать состояния друг у друга, а первый процесс ходит бесконечно.
Поэтому рано или поздно он перейдёт на состояние, которое не совпадает ни с одним из оставшихся $N-1$ состоянием.

'''Лемма''': через $O(N^2)$ после этого система стабилизируется.
'''Альтернативное доказательство (не с лекции)''': это состояние будет сразу же скопировано на второй процесс, потом сразу же скопировано на третий, и так далее, после чего мы прийдём в состояние, где все значения равны, а оно легальное.

== Поиск остовного дерева ==
Такая задача возникает, например, в internet of things: набросали с вертолёта на поле размером 3км*3км много хрупких устройств со слабыми антеннами, которым надо соединиться в единую сеть. При этом топология связи там неполная и половина устройств подохла.
А мы хотим построить дерево, чтобы узлы могли друг с другом общаться (а не каждый каждому передавать, потому что тогда надо бороться с циклами).

Решение начинается с инициатора (например, узел, которому надо что-нибудь узнать про всех остальных), которому это дерево нужно.

Каждый узел поддерживает у себя $d$ (расстояние до корня) и $p$ (узел-предок в дереве).
Корень всегда ставит у себя $d=0$ и $p=-1$, а остальные узлы в постоянном режиме делают:
* Найти соседа $j$ с минимальным $d_j$
* Установить его в качестве своего родителя и $d_i=d_j+1$

Тогда корень стабилизируется сразу, узлы, которым корень виден, стабилизируются через одну итерацию, их соседи — через две, и так далее.

Если какой-нибудь узел выпадает, то его дети найдут себе кого-нибудь ещё и снова встроятся в дерево.

Единственная проблема — если умирает корень, но тогда узнавший об этом узел может инициировать перестроение дерева (если у нас цель — связь).

Gossip-протоколы

2019-06-03T21:02:34Z

Yeputons:

[[Категория: Параллельное программирование]]
'''Gossip-протоколы''' — семейство протоколов, которые позволяют обеспечивать eventual consistency в распределённой системе.
В [[CAP-теорема|CAP-теореме]] они жертвуют согласованностью, получают доступность и устойчивость к разделению.

Основная идея: узлы распространяют информацию об изменениях друг другу по мере возможности, причём не только самостоятельно добавленные изменения, но и то, что услышали от других узлов (слухи, gossip).
Тогда при отсутствии сбоев рано или поздно все узлы обо всём узнают.
Разумеется, могут появиться конфликты, их надо как-нибудь решать.
Можно либо спускать эту задачу на уровень приложения (Amazon Dynamo), либо использовать специальные конструкции для распространения слухов вроде [[CRDT]], которые не допускают конфликтов по построению.

Точные протоколы общения процессов и распространения слухов мы не разбирали и они, говорят, не так важны.

CAP теорема

2019-06-03T21:02:27Z

Yeputons:

[[Категория: Параллельное программирование]]
'''CAP-теорема''' — утверждение о том, что в распределённых системах нельзя одновременно добиться трёх свойств:
* '''C'''onsistency — на всех ''не отказавших'' узлах одинаковые (с точки зрения пользователя) данные
* '''A'''vailability — запросы ко всем ''не отказавшим'' узлам возвращают ответ
* '''P'''artition tolerance — даже если связь в системе стала нестабильной (вплоть до разделения системы на куски), то система продолжает работать

Формально мы это не формулировали и не доказывали.
Оригинальная формулировка — Brewer's Conjecture (2000), а формализовано в работе Gilbert & Lynch (2004).
Там есть много тонкостей с тем, что такое "не отказавший узел", "одинаковые данные", "разрыв связи", "система продолжает работать", "когда система всё-таки окончательно ломается и считается недоступной" и тому подобное.

Для общей эрудиции выглядят неплохо статьи<ref>http://blog.thislongrun.com/2015/04/the-unclear-cp-vs-ca-case-in-cap.html</ref><ref>https://habr.com/ru/post/322276/</ref>

== Классификация алгоритмов ==
А вот алгоритмы, которые удовлетворяют хотя бы двум свойствам, можно нарисовать на диаграмма Венна:

[[Файл:Distributed-cap.png|400px]]

Дальше идут объяснения с лекции, они отличаются в разных источниках (например, где-то 2PC идёт вместе с Paxos в CP, а не в CA<ref>http://www.cedanet.com.au/ceda/fallacies/cap-theorem.php</ref>), а где-то совпадают с лекцией<ref>http://book.mixu.net/distsys/single-page.html#the-cap-theorem</ref>, а где-то считают, что не-partition tolerance не нужно<ref>https://codahale.com/you-cant-sacrifice-partition-tolerance/</ref>.
* Если мы хотим согласованность и доступность, то используем [[2 Phase Commit|протокол двухфазного коммита]]: он гарантирует нам согласованное состояние глобально во всей системе и мы всегда можем обслуживать запросы. Но если потерялась связь, то какие-то запросы нельзя обработать, потому что часть данных может быть на одном узле, а часть на другом. Каждый кусок всё ещё будет работать по отдельности, но глобальные транзакции выполнять мы не сможем.
* Иногда нам не так важна согласованность и мы согласны на простую eventual consistency — это когда информация может быть доступна не сразу везде, а только через какое-то время, если система здорова. Сюда идут [[gossip-протоколы]].
* Если мы хотим согласованность и толерантность к разделению, то надо жертвовать доступностью. Например, при помощи Paxos мы можем хранить все данные сразу на всех узлах, но тогда узлы, оказавшиеся в меньшинстве, ничего сделать не могут.

2 Phase Commit

2019-06-03T21:02:23Z

Yeputons:

[[Категория: Параллельное программирование]]
'''Алгоритм двухфазного коммита''' — классический централизованный оптимистичный алгоритм распределённого консенсуса из баз данных для подтверждения [[Транзакции в распределённых системах|распределённых транзакций]].

После того, как мы завершили транзакцию, её надо атомарно подтвердить на всех участниках.
У каждой транзакции есть выделенный координатор (transaction coordinator).
Алгоритм работает в две фазы:

# '''Запрос (request)''': координатор спрашивает каждого участника: "готов ли ты ''очень быстро и гарантированно'' завершить транзакцию?". Если кто-нибудь ответил "нет", то отменяем транзакцию. Если кто-то отвечает "да", то он должен уметь обеспечить завершение транзакции даже если упадёт и поднимается (например, все данные уже в журнале).
# '''Завершение''': координатор принимает решение о закреплении (commit) или отмене (rollback) транзакции и записывает его в свою надёжную память, после чего рассылает всем решение. После рассылки можно сообщить о фиксации транзакции, подтверждения от участников ждать не нужно (но тогда может быть проблема с тем, что следующие чтения из СУБД будут возвращать старые данные, пока не закоммитили).

При этом проблемы двух генералов на практике обычно нет: после того, как координатор принял решение о транзакции, он будет его доносить до всех любопытствующих узлов.

== Ограничения ==
Так как это алгоритм консенсуса, к нему применима [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]].

Если у нас есть отказы узлов или связи, то 2PC будет ждать, пока связь не восстановится:
* Если отказ произошёл на первой фазе, то координатор может отменить транзакцию по таймауту.
* После того, как координатор перешёл на вторую фазу, он не имеет права успокоиться, пока не донесёт своё решение до всех узлов.
* Если узел отказал, а потом восстановился, то он спрашивает координатора, какое решение было принято. Если "да", то обязан закрепить транзакцию (т.е. координатор должен хранить все подтверждённые транзакции, которые подтвердили не все узлы).
* Если отказал координатор, то, если узел ответил "да", он не имеет права забить на транзакцию, пока координатор не восстановится.

Но алгоритм классический, простой, на практике неплохо работает, потому что сложно только с отказами координатора и отказами узлов на второй фазе (когда решение о коммите уже принято), а такое бывает не так часто.

2 Phase Locking

2019-06-03T21:02:16Z

Yeputons:

[[Категория: Параллельное программирование]]
'''Алгоритм двухфазной блокировки''' используется для взятия блокировок при выполнении [[Транзакции в распределённых системах|распределённых транзакций]] (например, в СУБД).

Алгоритм требует, чтобы каждая транзакция должна состояла из двух фаз: на первой мы только набираем блокировки (в любом порядке), а на второй фазе мы их только отпускаем (в любом порядке).
Например, если мы работаем с элементами $x$ и $y$, то мы можем сначала взять блокировку на $x$, потом поработать с $x$, потом взять блокировку на $y$, поработать с ним, а потом отпустить все блокировки.

[[Файл:distributed-2pl.png|400px]]

Если все транзакции устроены таким образом, то гарантируется сериализуемость транзакции.

== Применение ==
Так можно брать не все блокировки, а только нужные.
Это особенно удобно в СУБД, когда движок заранее не знает, какие блокировки потребуются: он может просто набирать блокировки, как появляются запросы, а в конце, при применении транзакции, их разом отпустить.

Из-за этого могут возникнуть проблемы с взаимными блокировками (потому что порядок взятия блокировок может отличаться в разных транзакциях), поэтому:
* [[Определение взаимной блокировки|Детектор взаимных блокировок]] всё равно нужен. Если нашли — то отменяем одну из транзакций и снимаем все её блокировки. Есть разные стратегии выбора, какую транзакцию отменять. Можно самую новую (тогда мы будем дожидаться старой), можно самую долго работающую (тогда у коротких запросов приоритет), можно ещё как-то.
* В некоторых СУБД есть даже специальный SQL-синтаксис для deadlock avoidness, вроде <code>SELECT FOR UPDATE</code>

Проблемы, конечно, в том, что если у нас большой запрос по всем строкам таблицы, то нам нужно всё заблокировать, но для этого есть [[Транзакции в распределённых системах#Согласованность и изоляция|MVCC]] или пониженные уровни изоляции.

Транзакции в распределённых системах

2019-06-03T21:02:12Z

Yeputons:

[[Категория: Параллельное программирование]]
== Зачем ==

Пусть у нас есть несколько узлов (процессов), которых хранят какие-то ''непересекающиеся'' данные.
Например, на одном узле хранятся банковские счета пользователей на "А", на другом — на "Б", и так далее.

Тогда мы можем хотеть транзакционно изменять данные на разных узлах (см. <code>BEGIN TRANSACTION</code> и <code>COMMIT TRANSACTION</code> в SQL).
{{Определение
|definition=
'''Транзакция''' — это единица работы над множеством элементов из базы данных, которую можно в процессе работы целиком '''отменить''' (либо сама база данных, либо пользователь, см. <code>ROLLBACK TRANSACTION</code>), либо '''подтвердить''' (база данных может иногда не справиться, тогда транзакция отменяется).
}}
У транзакции обычно выделяют свойства по аббревиатуре ACID:
# '''A'''tomicity (атомарность) — транзакция либо полностью '''применила''' все свои изменения, либо полностью '''откатилась''' (отменилась)
# '''C'''onsitency (согласованность) — в конце транзакции система находится в согласованном состоянии
# '''I'''solation (изолированность) — параллельные транзакции не должны влиять друг на друга (например, при помощи phantom reads и non-repeatable reads), а должны выполняться как будто последовательно
# '''D'''urability (надёжность) — завершённые (commited) транзакции сохраняются даже в случае сбоев и перезапуска системы

== Атомарность и надёжность ==
Предположим, что нам нужны только атомарность и надёжность.
Самое сложное — откатывать транзакцию, если что-то пошло не так.
Есть два основных способа этого добиться.

=== Undo log ===
Каждый узел сначала записывает предыдущие значения в надёжный журнал (лог, обычно append-only и сохраняется на диск), а только потом изменяет состояние в памяти.
Когда транзакция подтверждается, надо записать произведённые изменения в надёжное место и можно стереть кусок журнала.
Если транзакцию надо откатить (например, после перезапуска системы в журнале нет записи "транзакция успешна"), то мы идём с конца журнала и восстанавливаем старые значения.

=== Redo log ===
Мы вообще не делаем изменения в данных до подтверждения транзакции, а просто пишем в журнал все операции, которые надо произвести с данными.
Когда транзакция успешно завершается, у нас две опции:
* Изменить данные прямо на диске.
* Записать об этом в журнал на диск (append-only), а состояние просто каждый раз восстанавливать из этого журнала. Иногда делать checkpoint'ы для сохранения состояния. Это сейчас на практике популярнее.

== Согласованность и изоляция ==
В базах данных различают разные уровни изоляции (isolation level), максимальный уровень — сериализуемость (serializability).
Это когда все транзакции можно упорядочить и получить согласованную историю, как если бы они выполнялись последовательно.

Можно брать блокировку сразу на все узлы, но это не очень эффективно и распределённая блокировка — это сложно, поэтому обычно дают блокировки разным данным в пределах одного узла.
Чтобы сделать транзакцию, надо взять нужные блокировки (даже на чтение) и отпустить их, но при этом не вляпаться во взаимные блокировки или несогласованность (по-факту то транзакция не мгновенная).
Для этого используется [[2 Phase Locking|алгоритм двухфазной блокировки]].

Более сложная штука — MVCC (MultiVersion Concurrency Control), это когда мы для каждой транзакции создаём "снимок" базы данных (наверняка при помощи персистентных структур данных)
и дальше транзакция работает с ним.
Например, в транзакциях только на чтение это позволяет экономить блокировки.
А если появились записи, то надо как-то пробовать решать конфликты или даже просто откатывать транзакцию, если данные, которые она читала, уже кем-то были изменены.

== Подтверждение транзакции в распределённой системе ==
Блокировки у нас локальны и берутся просто, но нам надо, чтобы все участники атомарно пришли к решению завершать транзакцию.
Можно использовать алгоритмы распределённого консенсуса, но они сложные.
Классическое решение в базах данных — [[2 Phase Commit|алгоритм двухфазного коммита]] (не имеет никакого отношения к двухфазной блокировке).

Самостабилизирующиеся алгоритмы

2019-06-03T21:00:43Z

Yeputons: /* Поиск остовного дерева */

{{Определение
|definition=
'''Самостабилизирующие алгоритмы''' — это идея построения алгоритмов, устойчивых к ошибкам:
* Код потерять сложно, поэтому мы считаем, что он не портится при падении узлов.
* Алгоритм может работать с любой комбинацией данных.
* Из любого состояния мы попадаем в '''легальное''' через конечное число шагов (при отсутствии сбоев).
}}
Тогда от ''любого'' сбоя мы через конечное число шагов будем восстанавливаться без консенсусов и прочих развлечений.
== Взаимное исключение ==
Dijkstra Stabilizing Token Ring Algorithm.

Сначала надо переформулировать задачу: мы говорим, что каждый процесс в системе может либо '''иметь привилегию''', либо не иметь.
В произвольном состоянии системы привилегия может быть у произвольного количества процессов, но через конечное число шагов она остаётся только у одного процесса и мы входим в легальное состояние.
Дальше остаёмся только в легальных состояниях.

TODO: а какие сообщения процессы посылают друг другу? Могут ли быть ошибки (наверное, нет)? Может ли система быть асинхронной (наверное, тоже нет)?

Все $N$ процессов будут замкнуты в кольцо, в котором один процесс назван "первым".
У каждого процесса есть состояние — число от 0 до $K-1$, причём $K \ge N$ — параметр алгоритма.

По определению положим, что у процесса есть привилегия, если:
* Он первый и его значение $S$ совпадает со значением $L$ следующего по часовой стрелке процесса.
* Он не первый и его $S$ не совпадает с $L$.

Например, на рисунке ниже толстая граница у выделенного процесса, а жёлтым обозначена привилегия:

[[Файл:distributed-self-stabilization-legal.png|400px]]

Правила перехода в новое состояние:
* Для первого процесса: если была привилегия ($S=L$), то переходим в состояние $(S + 1) \bmod K$
* Для не-первого процесса: если привилегия есть ($S \neq L$), то переходим в состояние $
Пример двух переходов:

[[Файл:Distributed-self-stabilization-step-1.png|400px]]

[[Файл:Distributed-self-stabilization-step-2.png|400px]]

Таким образом, в легальном состоянии привилегия у нас ходит по кругу, как в алгоритме с токеном.
Но там потеря токена была смертельной для алгоритма, а у нас — не смертельна.

=== Доказательство стабилизируемости ===
'''Лемма''': в любом состоянии хотя бы у одного процесса есть привилегия.
В противном случае у нас, с одной стороны, все значения машин равны друг другу (потому что для каждой машины, кроме первой, её значение совпадает со следующей по кругу), а с другой стороны значение первой машины и её соседа должны отличаться, противоречие.

'''Лемма''': что бы не происходило в системе, через $O(N^2)$ шагов в системе первый процесс сделает ход.
'''Доказательство (с лекции)''': если первый процесс не делает ход, то следующий за ним против часовой стрелки процесс 2 сможет сделать максимум один ход: взять себе значение первого процесса.
Процесс 3 после каждого хода процесса 2 может сделать максимум один ход: взять себе значение процесса 2.
То есть процесс 3 может сделать не больше двух ходов (один исходно, один после хода процесса 2).
Аналогично, процесс 4 может сделать не больше трёх ходов, и так далее.
Итого мы получаем, что если первый процесс не делает шаги, то через $O(N^2)$ шагов привилегия полностью исчезнет, чего не бывает.

'''Альтернативное доказательство (проверено рандомом)''': если первый процесс может сделать ход сразу, то всё доказали.
Иначе у него нет привилегии.
Заметим, что если следующий за ним по часовой стрелке процесс 2 либо имеет значение, равное ему, либо отличающееся (тогда он имеет привилегию и сразу делает ход).
Таким образом, через один ход процессы 1 и 2 имеют одинаковые значения.
Аналогично, через два хода процессы 1, 2 и 3 имеют одинаковые значения.
А через $N-1$ шаг все процессы гарантированно имеют одинаковые значения (если первый процесс так и не походил).
Таким образом, через $N-1$ шаг у первого процесса появляется привилегия и он ходит, $N=O(N^2)$.

'''Лемма''': рано или поздно у первого процесса будет уникальное $S$.
'''Доказательство''': все остальные процессы умеют только копировать состояния друг у друга, а первый процесс ходит бесконечно.
Поэтому рано или поздно он перейдёт на состояние, которое не совпадает ни с одним из оставшихся $N-1$ состоянием.

'''Лемма''': через $O(N^2)$ после этого система стабилизируется.
'''Альтернативное доказательство (не с лекции)''': это состояние будет сразу же скопировано на второй процесс, потом сразу же скопировано на третий, и так далее, после чего мы прийдём в состояние, где все значения равны, а оно легальное.

== Поиск остовного дерева ==
Такая задача возникает, например, в internet of things: набросали с вертолёта на поле размером 3км*3км много хрупких устройств со слабыми антеннами, которым надо соединиться в единую сеть. При этом топология связи там неполная и половина устройств подохла.
А мы хотим построить дерево, чтобы узлы могли друг с другом общаться (а не каждый каждому передавать, потому что тогда надо бороться с циклами).

Решение начинается с инициатора (например, узел, которому надо что-нибудь узнать про всех остальных), которому это дерево нужно.

Каждый узел поддерживает у себя $d$ (расстояние до корня) и $p$ (узел-предок в дереве).
Корень всегда ставит у себя $d=0$ и $p=-1$, а остальные узлы в постоянном режиме делают:
* Найти соседа $j$ с минимальным $d_j$
* Установить его в качестве своего родителя и $d_i=d_j+1$

Тогда корень стабилизируется сразу, узлы, которым корень виден, стабилизируются через одну итерацию, их соседи — через две, и так далее.

Если какой-нибудь узел выпадает, то его дети найдут себе кого-нибудь ещё и снова встроятся в дерево.

Единственная проблема — если умирает корень, но тогда узнавший об этом узел может инициировать перестроение дерева (если у нас цель — связь).

Самостабилизирующиеся алгоритмы

2019-06-03T20:49:28Z

Yeputons: /* Взаимное исключение */

Файл:Distributed-self-stabilization-step-2.png

2019-06-03T20:13:11Z

Yeputons:

Файл:Distributed-self-stabilization-step-1.png

2019-06-03T20:12:45Z

Yeputons:

Файл:Distributed-self-stabilization-legal.png

2019-06-03T20:09:55Z

Yeputons:

Самостабилизирующиеся алгоритмы

2019-06-03T19:45:55Z

Yeputons:

Самостабилизирующиеся алгоритмы

2019-06-03T19:45:28Z

Yeputons: Новая страница: «{{Определение |definition= '''Самостабилизирующие алгоритмы''' — это идея построения алгоритмо…»

Централизованный алгоритм для WCP

2019-06-03T19:43:29Z

Yeputons: /* Часы с прямой зависимостью вместо векторных */

[[Категория: Параллельное программирование]]
'''Централизованный алгоритм для WCP''' – алгоритм для поиска наименьшего (проще говоря, самого левого) [[Срез, согласованный срез|согласованного среза]] в котором выполняется [[Слабый конъюнктивный предикат (WCP)|слабый конъюнктивный предикат]].
Если есть хотя бы один согласованный срез, в котором выполняется слабый конъюнктивный предикат, то такой срез существует и единственен (см. [[слабый конъюнктивный предикат]]).

В централизованном алгоритме используются [[Векторные часы|векторные часы]]. Срез задается набором векторных часов для всех процессов или просто вектором, в котором соответствующая компонента показывает время для соответствующего потока.

Суть алгоритма:
* Есть один процесс-координатор, ответственный за поиск согласованного среза.
* Остальные процессы обычные, их задача — проверять свои локальные предикаты.
* Всякий раз, когда впервые с момента последнего отправленного сообщения локальный предикат становится true, оповещаем об этом координатора, указывая свое векторное время (впервые — чтобы не спамить, состояния процесса между посылками сообщений для системы неотличимы). Векторное время при этом увеличивается.
** Из этого следует, что если есть наименьший согласованный срез, в котором слабый конъюнктивный предикат верен, то в нём векторные часы всех потоков попарно несравнимы.
** Более того: если у нас есть срез (необязательно согласованный), в котором все векторные часы всех потоков попарно несравнимы, то он согласован (см. [[Срез, согласованный срез|согласованный срез]]).
** Таким образом нам достаточно искать наименьший срез из событий, в которых выполняется локальный предикат, а все векторные часы попарно несравнимы.
* Координатор поддерживает в памяти срез-кандидат и очередь необработанных сообщений от каждого процесса. Инвариант: все срезы, у которых хотя бы одна компонента меньше нашего среза-кандидата, гарантированно не подходят.
* Координатор хранит вектора среза-кандидата и флажок для каждой его компоненты: красный – это событие не может быть последним для данного процесса в срезе-кандидате (т.е. нет согласованного среда с верным предикатом, в котором в данном процессе в срез взяты события до данного или раньше), зеленый – может.
* Начальное состояние – все по нулям, красные;
* Обрабатываем приходящие сообщения только от красных процессов, сообщения от зеленых ставим в очередь.
** Пришедший от красного процесса вектор гарантированно попадает в срез-кандидат.
** Сравниваем пришедший вектор попарно с другими процессами. Если новый вектор больше, то делаем меньший процесс красным, потому что новый вектор гарантированно попадает, а тогда после меньшего вектора должно идти что-то ещё (иначе не получим попарно несравнимые события).
** После обработки сообщения делаем бывший красный процесс зеленым.
* Если все зеленое, то мы нашли согласованный срез.

Пример с найденным согласованным срезом, тут координатор по очереди сделал зелёными все процессы:

[[Файл:wcp-search-central-good.png|600px]]

Пример с не найденным согласованным срезом, тут координатор сначала сделал зелёным $P$, потом сделал зелёным $S$, а потом получил мажорирующий их вектор от $Q$ и сделал всех красными, кроме $Q$:

[[Файл:wcp-search-central-bad.png|600px]]

Итого центральному координатору требуется $O(N^2m)$ времени и памяти в сумме ($N$ — количество процессов, $m$ — количество сообщений от одного процесса).
Всего сообщений на алгоритм — $O(Nm)$.

== Оптимизации ==
=== Уменьшение количества посылок о выполнении предиката ===
Если в каком-то процессе выполнялся предикат, а потом он получил сообщение, то не надо ещё раз высылать сообщение координатору.
Доказательство: если бы было решение, где новое состояние процесса после получения сообщения было границей искомого среза, то мы можем сдвинуть это состояние назад. Предикат всё ещё будет выполняться, а срез менее согласованным не станет, т.к. получения сообщений можно выкидывать безболезненно.

На лекции, впрочем, говорилось, что не надо посылать даже если мы просто получили сообщение и предикат стал выполняться.

=== Часы с прямой зависимостью вместо векторных ===
Если ''каждый'' процесс участвует в вычислении предиката, то нам хватает [[Часы с прямой зависимостью|часов с прямой зависимостью]] вместо векторных.

Смысл в том, чтобы все процессы, которые хоть как-то влияют на предикат, общались напрямую с координатором.

Доказательство: TODO (на лекции не было).

Централизованный алгоритм для WCP

2019-06-03T19:40:31Z

Yeputons: /* Уменьшение количества посылок о выполнении предиката */

Централизованный алгоритм для WCP

2019-06-03T19:37:29Z

Yeputons: /* Оптимизации */

[[Категория: Параллельное программирование]]
'''Централизованный алгоритм для WCP''' – алгоритм для поиска наименьшего (проще говоря, самого левого) [[Срез, согласованный срез|согласованного среза]] в котором выполняется [[Слабый конъюнктивный предикат (WCP)|слабый конъюнктивный предикат]].
Если есть хотя бы один согласованный срез, в котором выполняется слабый конъюнктивный предикат, то такой срез существует и единственен (см. [[слабый конъюнктивный предикат]]).

В централизованном алгоритме используются [[Векторные часы|векторные часы]]. Срез задается набором векторных часов для всех процессов или просто вектором, в котором соответствующая компонента показывает время для соответствующего потока.

Суть алгоритма:
* Есть один процесс-координатор, ответственный за поиск согласованного среза.
* Остальные процессы обычные, их задача — проверять свои локальные предикаты.
* Всякий раз, когда впервые с момента последнего отправленного сообщения локальный предикат становится true, оповещаем об этом координатора, указывая свое векторное время (впервые — чтобы не спамить, состояния процесса между посылками сообщений для системы неотличимы). Векторное время при этом увеличивается.
** Из этого следует, что если есть наименьший согласованный срез, в котором слабый конъюнктивный предикат верен, то в нём векторные часы всех потоков попарно несравнимы.
** Более того: если у нас есть срез (необязательно согласованный), в котором все векторные часы всех потоков попарно несравнимы, то он согласован (см. [[Срез, согласованный срез|согласованный срез]]).
** Таким образом нам достаточно искать наименьший срез из событий, в которых выполняется локальный предикат, а все векторные часы попарно несравнимы.
* Координатор поддерживает в памяти срез-кандидат и очередь необработанных сообщений от каждого процесса. Инвариант: все срезы, у которых хотя бы одна компонента меньше нашего среза-кандидата, гарантированно не подходят.
* Координатор хранит вектора среза-кандидата и флажок для каждой его компоненты: красный – это событие не может быть последним для данного процесса в срезе-кандидате (т.е. нет согласованного среда с верным предикатом, в котором в данном процессе в срез взяты события до данного или раньше), зеленый – может.
* Начальное состояние – все по нулям, красные;
* Обрабатываем приходящие сообщения только от красных процессов, сообщения от зеленых ставим в очередь.
** Пришедший от красного процесса вектор гарантированно попадает в срез-кандидат.
** Сравниваем пришедший вектор попарно с другими процессами. Если новый вектор больше, то делаем меньший процесс красным, потому что новый вектор гарантированно попадает, а тогда после меньшего вектора должно идти что-то ещё (иначе не получим попарно несравнимые события).
** После обработки сообщения делаем бывший красный процесс зеленым.
* Если все зеленое, то мы нашли согласованный срез.

Пример с найденным согласованным срезом, тут координатор по очереди сделал зелёными все процессы:

[[Файл:wcp-search-central-good.png|600px]]

Пример с не найденным согласованным срезом, тут координатор сначала сделал зелёным $P$, потом сделал зелёным $S$, а потом получил мажорирующий их вектор от $Q$ и сделал всех красными, кроме $Q$:

[[Файл:wcp-search-central-bad.png|600px]]

Итого центральному координатору требуется $O(N^2m)$ времени и памяти в сумме ($N$ — количество процессов, $m$ — количество сообщений от одного процесса).
Всего сообщений на алгоритм — $O(Nm)$.

== Оптимизации ==
=== Уменьшение количества посылок о выполнении предиката ===
Если в каком-то процессе выполнялся предикат, а потом он получил сообщение, то не надо ещё раз высылать сообщение координатору.
Доказательство: если бы было решение, где новое состояние процесса после получения сообщения было границей искомого среза, то мы можем сдвинуть это состояние назад. Предикат всё ещё будет выполняться, а срез менее согласованным не станет, т.к. получения сообщений можно выкидывать безболезненно.

=== Часы с прямой зависимостью вместо векторных ===