Консенсус в синхронных системах — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
[[Категория:Параллельное программирование]]
 
[[Категория:Параллельное программирование]]
 
Как известно из [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]], при всех требованиях консенсус невозможен. Уберем требование асинхронности (любое сообщение доходит за некоторое конечное время).
 
Как известно из [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]], при всех требованиях консенсус невозможен. Уберем требование асинхронности (любое сообщение доходит за некоторое конечное время).

Текущая версия на 19:37, 4 сентября 2022

Как известно из FLP, при всех требованиях консенсус невозможен. Уберем требование асинхронности (любое сообщение доходит за некоторое конечное время).

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

Но можно решить задачу консенсуса за f+1 фазу (секция 15.4.1 на странице 240 в Garg):

  • Делаем в каждом узле множество из n значений (своё записываем, остальные пока неизвестны)
  • В каждом раунде каждый узел посылает каждому все свои числа (или только те, которые не посылал ранее - без разницы)
  • Процессы записывают пришедшие числа в свой вектор
  • После f+1 - го раунда выбираем минимум из известных чисел.

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

А если рассылаем только новые данные, то интереснее (см. Garg; на лекции вроде не было). Пусть у неотказавшего процесса $P_i$ после раунда $f+1$ есть значение $x$. Тогда если он его получил в раунде $f$ или меньшем, то в раунде $f+1$ он разошлёт его всем остальным и все неотказавшие его успешно получат. Более интересный случай: процесс $P_i$ получил значение $x$ только в раунде $f+1$, а в предыдущих $f$ не получал. Предположим, что есть процесс $P_j$, который так и не получил значение $x$ к раунду $f+1$. Тогда у нас имеется $f+1$ процесс, которые по очереди отказывали на предыдущих шагах, успевая передать друг другу $x$, но не успевая передать их $P_i$ или $P_j$. И только $(f+1)$-й отказавший процессор смог передать $P_i$, но не $P_j$. Но у нас всего максимум $f$ отказов, противоречие.

Итого нам требуется $O((f + 1)N^2)$ сообщений на консенсус.