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

Версия 14:10, 30 января 2019

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

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

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

Рабочая таблица: https://docs.google.com/spreadsheets/d/1zvAqjpLXExVKFC5dHbnvWVJLNseUYKXKu5e0wSrvwUQ/edit?usp=sharing

Оценка за НИС формируется из двух компонент: 1. Выполненное практическое задание (должно скоро появиться ;) -- 4 балла за задание 2. Доклад (один или более) на семинаре -- 3 балла за один доклад 3. Рецензия (одна или более) -- 3 балла за одну рецензию

Доклад

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

Продолжительность доклада ограничена 20 минутами. После доклада отводится 5 минут на вопросы слушателей. На одном занятии проводится до 3 докладов.

Расписание докладов доступно в таблице по ссылке: https://docs.google.com/spreadsheets/d/1zvAqjpLXExVKFC5dHbnvWVJLNseUYKXKu5e0wSrvwUQ/edit?usp=sharing.

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

Рецензия

Рецензия подразумевает самостоятельное изучения научной статьи и написание краткого обзора статьи. Формат задания аналогичен прошлогоднему.

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

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

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

Для сдачи рецензии необходимо записаться в табличку -- https://docs.google.com/spreadsheets/d/1zvAqjpLXExVKFC5dHbnvWVJLNseUYKXKu5e0wSrvwUQ/edit?usp=sharing -- и прислать до окончания курса на почту sandello@gmail.com письмо с темой "НИС РС 155 - Рецензия - Фамилия Имя".

Список статей для докладов и рецензирования

1. Ghemawat S., Gobioff H., Leung S.T. The Google File System // ACM Symposium on Operating Systems Principles (SOSP), 2003.
2. Dean J., Ghemawat S. MapReduce: simplified data processing on large clusters // USENIX Symposium on Operating System Design and Implementation (OSDI), 2004.
3. Hayashibara N. et al. The φ accrual failure detector // Japan Advanced Institute of Science and Technology, School of Information Science, Technical Report IS-RR-2004-010, 2004.
4. Van Renesse R., Schneider F. B. Chain Replication for Supporting High Throughput and Availability // USENIX Symposium on Operating System Design and Implementation (OSDI), 2004.
5. Lamport L. Fast paxos //Distributed Computing. – 2006. – Т. 19. – №. 2. – С. 79-103.
6. Chang F. et al. Bigtable: A distributed storage system for structured data // USENIX Symposium on Operating System Design and Implementation (OSDI), 2006.
7. Mazieres D. Paxos made practical. Technical Report, Stanford University, 2007.
8. Chandra T. D., Griesemer R., Redstone J. Paxos made live: an engineering perspective //Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. – ACM, 2007. – С. 398-407.
9. Isard M. et al. Dryad: distributed data-parallel programs from sequential building blocks //ACM SIGOPS operating systems review. – ACM, 2007. – Т. 41. – №. 3. – С. 59-72.
10. DeCandia G. et al. Dynamo: Amazon's highly available key-value store // ACM Symposium on Operating Systems Principles (SOSP), 2007.
11. Cooper B. F. et al. PNUTS: Yahoo!'s hosted data serving platform // International Conference on Very Large Data Bases (VLDB), 2008.
12. Isard M. et al. Quincy: fair scheduling for distributed computing clusters //Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles. – ACM, 2009. – С. 261-276.
13. Van Renesse R., Minsky Y., Hayden M. A gossip-style failure detection service //Proceedings of the IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing. – Springer-Verlag, 2009. – С. 55-70.
14. Helland P., Campbell D. Building on quicksand // Conference on Innovative Data Systems Research (CIDR), January 2009.
15. Malewicz G. et al. Pregel: a system for large-scale graph processing // ACM International Conference on Management of Data (SIGMOD), 2010.
16. Hunt P. et al. ZooKeeper: Wait-free Coordination for Internet-scale Systems //USENIX annual technical conference. – 2010. – Т. 8. – №. 9.
17. Lakshman A., Malik P. Cassandra: a decentralized structured storage system //ACM SIGOPS Operating Systems Review. – 2010. – Т. 44. – №. 2. – С. 35-40.
18. Anderson E. et al. What consistency does your key-value store actually provide? // HotDep, 2010.
19. Terry D. Replicated data consistency explained through baseball // Microsoft Research, Technical Report MSR-TR-2011-137, 2011.
20. Junqueira F. P., Reed B. C., Serafini M. Zab: High-performance broadcast for primary-backup systems //Dependable Systems & Networks (DSN), 2011 IEEE/IFIP 41st International Conference on. – IEEE, 2011. – С. 245-256.
21. Shapiro M. et al. Conflict-free replicated data types // Symposium on Self-Stabilizing Systems, 2011.
22. Rao J., Shekita E. J., Tata S. Using paxos to build a scalable, consistent, and highly available datastore //Proceedings of the VLDB Endowment. – 2011. – Т. 4. – №. 4. – С. 243-254.
23. Calder B. et al. Windows Azure Storage: a highly available cloud storage service with strong consistency // ACM Symposium on Operating Systems Principles (SOSP), 2011.
24. Leners J. B. et al. Detecting failures in distributed systems with the falcon spy network //Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. – ACM, 2011. – С. 279-294.
25. Corbett J. C. et al. Spanner: Google’s globally distributed database // USENIX Symposium on Operating System Design and Implementation (OSDI), 2012.
26. Liskov B., Cowling J. Viewstamped replication revisited. Massachusetts Institute of Technology, Tech Report MIT-CSAIL-TR-2012-021, 2012.
27. Bronson N. et al. TAO: Facebook's Distributed Data Store for the Social Graph // USENIX Annual Technical Conference, 2013.
28. Murray D. G. et al. Naiad: a timely dataflow system // Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. – ACM, 2013. – С. 439-455.
29. Schwarzkopf M. et al. Omega: flexible, scalable schedulers for large compute clusters //Proceedings of the 8th ACM European Conference on Computer Systems. – ACM, 2013. – С. 351-364.
30. Ongaro D., Ousterhout J. K. In search of an understandable consensus algorithm // USENIX Annual Technical Conference, 2014.
31. Bernstein P. A. et al. Orleans: Distributed virtual actors for programmability and scalability // Microsoft Research Technical Report MSR-TR-2014-41, 2014.
32. Verma A. et al. Large-scale cluster management at Google with Borg // European Conference on Computer Systems (EuroSys), 2015.
33. Lu H. et al. Existential consistency: measuring and understanding consistency at Facebook // ACM Symposium on Operating Systems Principles (SOSP), 2015.
34. Howard H. et al. Raft refloated: do we have consensus? // ACM SIGOPS Operating Systems Review. – 2015. – Т. 49. – №. 1. – С. 12-21.
35. Van Renesse R., Altinbuken D. Paxos made moderately complex //ACM Computing Surveys (CSUR). – 2015. – Т. 47. – №. 3. – С. 42.
36. Burckhardt S. et al. Global sequence protocol: A robust abstraction for replicated shared state // LIPIcs-Leibniz International Proceedings in Informatics. – Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. – Т. 37.