Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Теория распределенных вычислений
Санкт-Петербург / осень 2019, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Курс посвящен теории, лежащей в основе современных промышленных распределенных систем: файловых систем, очередей сообщений, key/value хранилищ, баз данных. Эти системы хранят десятки и сотни петабайт данных, обслуживают многие тысячи запросов в секунду и масштабируются до сотен и тысяч машин, переживая при этом отказы дисков и питания, дрейф часов, задержки и нарушения связности сети, а потому устроены невероятно сложно.

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

В курсе мы сформулируем эти задачи, исследуем ограничения, которые накладывает на них модель сети и сбоев, и подробно разберем алгоритмы их решения, которые применяются в современных промышленных распределенных системах.

Лекции будут выстроены в одну историю: мы начнем с выбора модели распределенной системы и очень простой задачи построения отказоустойчивой ячейки памяти, на примере которой изучим ключевые техники дизайна распределенных алгоритмов, затем перейдем к общему механизму репликации через Atomic Broadcast и изучим его связь с задачей консенсуса и ключевые результаты о невозможности, подробно разберем известный алгоритм Paxos и выведем из него Multi-Paxos или RAFT, а завершим курс византийской моделью и Bitcoin-ом, на который посмотрим через призму изученных ранее классических результатов и алгоритмов.

Дата и время Название Место Материалы
23 ноября
17:15–18:45
Модель распределенной системы. Время, лекция ПОМИ РАН видео
23 ноября
19:00–20:30
Репликация и линеаризуемость. Алгоритм ABD репликации регистра, лекция ПОМИ РАН видео
24 ноября
11:15–12:45
Репликация с помощью Atomic Broadcast. AB, консенсус и FLP, лекция ПОМИ РАН видео
24 ноября
13:00–14:30
Алгоритм Single-Decree Paxos, лекция ПОМИ РАН видео
24 ноября
15:30–17:00
От Single-Decree Paxos к Multi-Paxos и RAFT, лекция ПОМИ РАН видео
30 ноября
17:15–18:45
Верификация распределенных систем, TLA+, лекция ПОМИ РАН Нет
30 ноября
19:00–20:30
Верификация распределенных систем, TLA+, лекция ПОМИ РАН Нет
01 декабря
11:15–12:45
Византийские сбои, лекция ПОМИ РАН Нет
01 декабря
13:00–14:30
Алгоритм PBFT, лекция ПОМИ РАН Нет
01 декабря
15:30–17:00
Bitcoin через призму классической теории, лекция ПОМИ РАН Нет