292
правки
Изменения
Новая страница: « Как известно из FLP, при всех требованиях консенсус невозможен. Уберем требование асинхр…»
Как известно из 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)$ сообщений на консенсус.
