CRDT: Полностью доступные распределённые системы
Преподаватель: Сыровецкий Юрий Алексеевич
Модуль: 4
Кредиты: 3
Аннотация:
Теория и практика построения высокодоступных и полностью доступных распределённых систем. Типы данных и алгоритмы CRDT как основа архитектуры доступной системы. Алгебра встречается с кодингом. Вы овладеете методами проектирования распределённых систем, сфокусированных на доступности и качестве сервиса для конечного пользователя. Научитесь создавать инструменты коллаборативного редактирования документов и мобильные приложения, продолжающие корректно работать в офлайне.
Для кого: Для студентов всех курсов бакалавриата и магистратуры, интересующихся методами построения многопользовательских систем и математическими подходами к проектированию распределённых приложений.
Требования: Умение программировать хотя бы на одном языке программирования высокого уровня.
Организация курса:
Курс продлится 12 недель. Еженедельно нужно будет посетить одно занятие и выполнить домашнее задание. Каждое занятие будет длиться 2 пары и состоять из теоретической и практической частей. Предполагается, что студенты будут приносить на занятия свои портативные компьютеры.
Предварительный список тем:
Согласованность, доступность, устойчивость к разделению. Теорема Брюэра и принцип PACELC. Строгая согласованность в конечном счёте. История совместных редакторов, Operational transformation.
Алгебра: полугруппа, моноид, полурешётка. Определение полурешётки через операцию и отношение.
Понятие причинной связи, отношение причинности. Время и часы Лэмпорта, гибридные часы. Уникальные идентификаторы, RFC 4122.
State-based CRDT, определение и примеры: LWW, max/min, G-counter, PN-counter, G-set, произведение типов.
Op-based CRDT, определение и примеры: LWW, max/min, G-counter, PN-counter, G-set, произведение типов.
Replicated Object Notation. Журнальная модель.
Представление множеств с помощью Observed-Removed Set. State-based и op-based подходы.
Словари и объекты на основе LWW и OR-set.
Представления последовательностей.
Replicated Growable Array с точки зрения state-base и op-based.
Представление произвольных последовательностей.
Представление текста и типичные проблемы при работе с текстовыми данными.
Представление последовательностей с помощью Causal Trees.
Проектирование распределённого полностью доступного приложения.
Недостатки CRDT и способы их обойти.
Как будут выставляться оценки:
На каждую изученную тему будет дано домашнее задание, заключающееся в реализации заданного математической модели на выбранном студентом языке программирования.
Расписание: суббота 14:40-16:00 и 16:20-17:40 с 10 апреля
Преподаватель: Сыровецкий Юрий Алексеевич
Модуль: 4
Кредиты: 3
Аннотация:
Теория и практика построения высокодоступных и полностью доступных распределённых систем. Типы данных и алгоритмы CRDT как основа архитектуры доступной системы. Алгебра встречается с кодингом. Вы овладеете методами проектирования распределённых систем, сфокусированных на доступности и качестве сервиса для конечного пользователя. Научитесь создавать инструменты коллаборативного редактирования документов и мобильные приложения, продолжающие корректно работать в офлайне.
Для кого: Для студентов всех курсов бакалавриата и магистратуры, интересующихся методами построения многопользовательских систем и математическими подходами к проектированию распределённых приложений.
Требования: Умение программировать хотя бы на одном языке программирования высокого уровня.
Организация курса:
Курс продлится 12 недель. Еженедельно нужно будет посетить одно занятие и выполнить домашнее задание. Каждое занятие будет длиться 2 пары и состоять из теоретической и практической частей. Предполагается, что студенты будут приносить на занятия свои портативные компьютеры.
Предварительный список тем:
Согласованность, доступность, устойчивость к разделению. Теорема Брюэра и принцип PACELC. Строгая согласованность в конечном счёте. История совместных редакторов, Operational transformation.
Алгебра: полугруппа, моноид, полурешётка. Определение полурешётки через операцию и отношение.
Понятие причинной связи, отношение причинности. Время и часы Лэмпорта, гибридные часы. Уникальные идентификаторы, RFC 4122.
State-based CRDT, определение и примеры: LWW, max/min, G-counter, PN-counter, G-set, произведение типов.
Op-based CRDT, определение и примеры: LWW, max/min, G-counter, PN-counter, G-set, произведение типов.
Replicated Object Notation. Журнальная модель.
Представление множеств с помощью Observed-Removed Set. State-based и op-based подходы.
Словари и объекты на основе LWW и OR-set.
Представления последовательностей.
Replicated Growable Array с точки зрения state-base и op-based.
Представление произвольных последовательностей.
Представление текста и типичные проблемы при работе с текстовыми данными.
Представление последовательностей с помощью Causal Trees.
Проектирование распределённого полностью доступного приложения.
Недостатки CRDT и способы их обойти.