НИС Распределенные системы (3 курс, 2017)

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

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

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

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

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

Оценка

  • Проверочная работа 1 <= 4 баллов
  • Задание 1 <= 3 баллов
  • Проверочная работа 2 <= 4 баллов
  • Задание 2 <= 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

TBA.

Источник — «http://wiki.cs.hse.ru/index.php?title=НИС_Распределенные_системы_(3_курс,_2017)&oldid=27907»