TFTDS / Лекция 4 / Невозможность консенсуса, теорема FLP
00:00:00 - Recap
00:08:23 - Эквивалентность AB и консенсуса, последствия
00:12:08 - Невозможность консенсуса при отказе половины узлов
00:24:42 - Интуиция: agreement при партишенах / termination при отказах
00:29:07 - Теорема FLP
00:34:46 - Моделирование алгоритма: конфигурации, переходы, граф конфигураций и траектории
00:39:00 - Ограничения для adversary
00:41:07 - Бинарный консенсус, валентность конфигураций
00:43:00 - План доказательства
00:48:43 - Лемма 1: Найдется начальная бивалентная конфигурация
00:53:24 - Лемма 2: Можно перейти в новую бивалентную конфигурацию. Шаг 1
00:59:14 - Лемма 2 / Шаг 2
01:06:36 - Лемма 2 / Шаг 3
01:15:03 - Строим бесконечное исполнение
01:17:20 - Разница между теоремами
01:19:08 - Мы не убиваем узлы!
01:21:55 - Детекторы сбоев, задача выбора лидера
Дата лекции: 25 сентября 2021
Лектор: Роман Липовский
Съёмка и монтаж: Дмитрий Купцов
Плейлист с лекциями:
• TFTDS (лекции, 3 курс, осень 2021) - Липов...
Плейлист с семинарами:
• TFTDS (семинары, 3 курс, осень 2021) - Лип...
