===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===
#Отказ одного или нескольких узлов (crash)#Отказ одного или нескольких каналов (link failure)#Ненадежная доставка сообщений (omission)#Византийская ошибка (byzantine failure) (сломавшийся процесс может слать любой мусор) * [[Иерархия ошибок строится по тому, что более сильные ошибки могут имитировать менее сильные - византийская ошибка имитирует поведение при ненадежной доставке сообщений, ненадежная доставка может имитировать полный отказ канала, а отказ всех каналов к узлу - отказ узла. Невозможность консенсуса в асинхронной системе с отказом узла (FLP)(Фишер-Линч-Патерсон) 4 требования/предпосылки:* Система асинхронна (нет предела времени доставки сообщения)* (Один) узел может отказать (crash)распределённых системах]]* [[Консенсус надо достичь за конечное времяв распределённой системе]]* Детерминированный алгоритм консенсуса '''ТЕОРЕМА''': Невозможно достичь консенсуса N процессам, даже на множестве значений из двух элементов 0 и 1 Соответственно, можно придти к консенсусу, если:* сделать сеть синхронной [[Теорема Фишера-Линча-Патерсона (ограничить время доставки сообщений)* сделать алгоритм недетерминированным (случайнымFLP)* ослабить требования при которых в алгоритме обязан быть прогресс (т.е. он обязан завершаться) TODO: доказательство из презентации Елизарова.Инфо: http://bailonga.es/tpmtp/lecture09.pdf + презентация Р.Елизарова]]
===23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast===
