НИС Распределенные системы (3 курс, 2017) — различия между версиями

Текущая версия на 22:49, 15 июня 2018

Информация про семинар

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

Контакты: Пузыревский Иван Витальевич

Список тем курсовых работ: http://wiki.cs.hse.ru/Темы_для_курсовых_работ_2017_(РС)

Оценка

• Проверочная работа 1 <= 4 баллов
• Задание 1 <= 3 баллов
• Задание 4 <= 4 баллов
• Рецензирование статьи <= 3 баллов

Текущая таблица с оценками и ведомостью: https://docs.google.com/spreadsheets/d/16Z74fhT_TnNscsVviU9KU2mVlaMrmX3weQ6ku5jGGbk/edit?usp=sharing

Занятия

1 модуль

• Модель распределенных вычислений.
• Объекты-регистры, типы регистров (bool/int; safe/regular/atomic; single/multi-reader; single/multi-writer).
• Эквивалентность вычислительной силы SRSW Bool Safe & MRMW Int Atomic.
• Блокировки (locks). Понятия живости (liveness) и безопасности (safety). Мьютекс Лампорта.

Литература: Herlihy, Shavit -- The Art of Multiprocessor Programming (https://www.dropbox.com/s/s8sssgp95hq5f6q/aompp.pdf?dl=0). Главы 2-4.

2 модуль

• Lock-free & wait-free исполнения.
• Примитив консенсуса. Число консенсуса как характеристика примитивов синхронизации.
• Универальность консенсуса.

Литература: Herlihy, Shavit -- The Art of Multiprocessor Programming (https://www.dropbox.com/s/s8sssgp95hq5f6q/aompp.pdf?dl=0). Главы 5-6.

Работа над ошибками (всем): задачи 11-19, все; deadline: НИС неделе 15.01-21.01.

3 модуль

Распределенные алгоритмы. Время, часы, порядок на событиях.

Назначенные статьи для разбора на занятии:

• на 29.01; Богданова: Lamport -- Time, clocks and the ordering of events in a distributed system (pdf)
• на 29.01; Божко: Fidge -- Timestamps in message-passing systems that preserve the partial ordering (pdf)
• на 05.02; Когтенков: Mills -- Internet time synchronization: the network time protocol (pdf)

Литература: Garg -- Elements Of Distributed Computing.

4 модуль

Назначенные статьи для разбора на занятии:

• на 25.05; Кутенин: Liskov, Cowling -- Viewstamped replication revisited (pdf) + Oki, Liskov -- Viewstamped replication: a new primary copy method to support highly available distributed systems (pdf)
• на 08.06; Ренева: Ongaro, Ousterhout -- In search of understandable consensus algorithm (pdf) + Ousterhout -- Raft lecture (video; 1.0ч)

Задание 1

Заготовка: https://github.com/sandello/hse-queue-assignment

Дедлайн: 23 апреля 08:00.

Вам необходимо создать файл solution_xxx.cpp ("xxx" замените на вашу фамилию), содержащий реализацию lock-free многопоточной очереди с интерфейсом IQueue; в конце файла определить тип TheQueue. Далее, скомпилировать ваше решение можно с помощью скрипта compile.sh. Решение считается корректным, если скомпилированная программа корректно, без ошибок отрабатывает при запуске с флагом --gtest_repeat=100.

В качестве решения можно реализовать Michael-Scott Queue или очередь с использованием универсальной конструкции из второго модуля.

Ваше решение -- cpp-файл -- присылайте на почту sandello@gmail.com или присылайте ссылку на GH.

Задание 2

Заготовка: https://github.com/sandello/hse-paxos-assignment

Дедлайн: 9 июня 08:00.

Вам необходимо создать файл solution_xxx.py ("xxx" замените на вашу фамилию), содержащий реализацию процесса распределенного отказоустойчивого write-once key-value хранилища. Write-once значит, что каждый ключ можно записать не более, чем один раз (попытки перезаписи не приводят к изменению значения). Key-value store значит, что хранилище адресует пользовательские строковые данные по пользовательскому строковому ключу. Работа с данными по фиксированному ключу имеет семантику регулярного регистра. Распределенность и отказоустойчивость значат, что операции чтения и записи может обрабатывать любая реплика (экземпляр процесса), и остановка меньшей части реплик не останавливает процесс операций.

В задании предполагается следующая модель разработки: ваш процесс должен наследоваться от класса Process, определенном в файле public.py. Класс Process обладает тремя абстрактными методами: setup, on_tick, on_receive. Метод setup вызывается при инициализации теста и используется для передачи вашему процессу информации об окружении: в частности, о количестве процессов. Метод on_tick вызывается, когда конкретно данному процессу дается квант времени для внутренней работы. Метод on_receive вызывается при доставке данному конкретному процессу сообщения (в качестве сообщения можно использовать любой сериализуемый в json объект). В методы on_tick и on_receive передается контекст (ctx); объект контекста реализует интерфейс Context; контекст можно использовать для получения текущего (логического) времени и для отправки сообщения какому-либо другому процессу. Контекст нельзя сохранять и переиспользовать между разными вызовами on_tick и on_receive.

Такая модель разработки отражает теоретическую модель и позволяет эмулировать отказы и эффекты асинхронности в тестах. Не допускается порождать и использовать фоновые потоки (threads); ваш код должен быть однопоточным. Код тестов взаимодействует с вашим процессом путем отправки специальных сообщений а-ля RPC-запрос. Формат сообщения следующий: {"method": "M", "request_id": N, ...}. Код тестов отправляет запросы с M=get или M=set и ожидает получить в ответ (спустя некоторое количество шагов) в ответ структуру с ответом, аннотированную request_id.

Более точно, протокол взаимодействия следующий:

• {"method": "get", "request_id": N, "key": "K"} -> {"request_id": N, "value": "V"} ; запрос на чтение данных по ключу K (строка); в ответ ожидается значение V (строка).
• {"method": "set", "request_id": N, "key": "K", "value": "V"} -> {"request_id": N, "value": "W", "flag": "F"} ; запрос на запись данных V (строка) по ключу K (строка); в ответ приходит флаг-индикатор F исхода операции; если флаг истинен, то операция закончилась успешно, и в ячейку по ключу K было действительно сохранено значение V, и в таком случае возвращаемое значение W совпадает с V; если флаг ложен, то по каким-либо причинам операция записи закончилась неуспешно (заполненность ячейки / конкуренция при записи), и возвращается фактическое значение в ячейке W.
• в тестах чтение ключа K всегда идет строго после какой-либо успешной записи по ключу K.

Для запуска тестов используйте скрипт main.py. Ему необходимо передать путь до вашего класса в формате "МОДУЛЬ.КЛАСС". К примеру, main.py -i solution_puzyrevskiy_example.GlobalKeyValueStoreProcess. Для отладки передайте ключ -v.

Набор тестов скоро пополнится стресс-тестом. Если вы придумаете хороший, полезный тест, то присылайте PR.

Ваше решение -- py-файл и имя класса -- присылайте на почту sandello@gmail.com или присылайте ссылку на GH.

Задание 3

Ваша задача -- написать краткий обзор и рецензию научной статьи.

Дедлайн: 21 июня 19:00.

Что такое рецензия: это текст на 1-2 страницы, резюмирующий основные результаты работы, их отличительные характеристики и важные идеи. Если в статье описывается некоторая система -- то в рецензии стоит кратко определить (без воды) решаемую задачу, архитектуру системы, интерфейсы, протоколы. Если в статье описывается алгоритм -- важные технические характеристики (время работы, память, количество сообщений, и т. д.) и ключевые идеи. Если в статье описывается исследование -- то предмет исследования, методологию и выводы из исследования. Также, чтобы рецензия не была простым пересказом, вам обязательно в конце рецензии необходимо добавить собственный оценочный блок:

• как минимум три комментария по упомянутым в статье требованиям (условиям окружения, ограничениям на класс решений, предпосылкам, желаемым гарантиям системы, etc); каждый комментарий -- это цитата автора, определяющая требования + аргументация, почему требование неактуально / ослаблено / невыполнимо в других условиях. К примеру: "в работе авторы пишут: "так как мы планируем запускать протокол поверх SMS-сообщений, то ограничим длину каждого сообщения протокола 80 символами"; -> в настоящий момент меньше приложений используют SMS, предпочитая месседжеры".
• как минимум три комментария по принятым авторами дизайн-решениям в вопросах, допускающих альтернативные решения; каждый комментарий -- это краткая суть решаемой проблемы + описание принятого решения. К примеру: "авторы работы для валидации целостности контента сообщения используют чексумму, и дополнительно указывают отправителя в заголовке для аутентификации; возможно, более надежно было бы рассмотреть использование HMAC как альтернативы для одновременного контроля целостности и аутентификации".

Цель данного задания -- научиться видеть требования и граничные условия, во многом обуславливающие принимаемые авторами работы решения, а также уметь генерировать альтернативные варианты решения задач. За каждый валидный комментарий (в смысле определения выше) начисляется 0.5 балла. Итого за задание можно получить 3 балла.

Список доступных работ для рецензирования:

• Astrolabe
• Bayou
• Chord
• Dapper
• DNS
• Kademlia
• Swim
• можно предложить свою работу, предварительно её согласовав.

Регламент сдачи: 1. В таблице вписать свою фамилию в свободный слот. Каждую работу может рецензировать не более двух студентов. 2. Написать в Google Documents рецензию. 3. Прислать на sandello@gmail.com share-ссылку на документ с правами "Can Comment". В теме письма укажите номер группы и фамилию.