Пусть в системе имеется ''n'' узлов, каждому задано начальное число.
Пусть из них максимум ''f'' могут в любой момент упастьнавсегда (crash), "воскрешения" не разрешены.Тогда можно решить задачу консенсуса за ''f+1'' раундов[[Консенсус в распределённой системе#Решение при отсутствии отказов|базовый алгоритм]] всё ещё не работает, хотя мы и можем "дождаться всех сообщений":узел может отказать в процессе рассылки предложений: кому-то послал, а кому-то не успел.
Но можно решить задачу консенсуса за ''f+1'' фазу (секция 15.4.1 на странице 240 в Garg): *Делаем в каждом узле вектор множество из ''n'' значений (своё записываем, остальные пока неизвестны)
*В каждом раунде каждый узел посылает каждому все свои числа (или только те, которые не посылал ранее - без разницы)
*Процессы записывают пришедшие числа в свой вектор
*После ''f+1'' - го раунда выбираем минимум из известных чисел.
Почему это работает?ДопустимДокажем, что процессы a и b выбрали разные минимумыв конце у всех неотказавших процессов будут одинаковые множества значений. ЗначитЕсли мы на каждом шаге рассылаем вообще всё множество, то это просто: у нас по принципу Дирихле есть значение vраунд без ошибок, в нём все друг другу всё рассказали, а дальше множества уже не меняются. А если рассылаем только новые данные, которое есть то интереснее (см. Garg; на лекции вроде не было).Пусть у одного из процессов и нет у другого(пусть неотказавшего процесса $P_i$ после раунда $f+1$ есть у b)значение $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)$ сообщений на консенсус.
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
