Distributed Systems Course (fall 2012/2013)

Lecturer: Konrad Iwanicki
Assistants: none
Lectures: Wednesday, 2:15 PM - 3:45 PM, Room 3230
Excercise classes: Monday, 4:15 PM - 5:45 PM, Room 3240
Wednesday, 4:15 PM - 5:45 PM, Room 3150
Final exam: Thursday, January 31, 12:30 PM - 3:00 PM, Room 2070

This (third) edition of the course consists of two components: lectures and excercise classes. The lectures cover the principles, advanced concepts, and technologies of distributed systems, including communication, replication, fault tolerance, and security. The excercise part, in turn, consists of a series of student presentations of an educational value and recent papers from top systems conferences and journals. The course is recommended for graduate students attending the distributed systems seminar and other students interested in computer systems. The course can be given in English.

Passing Rules

To pass the course, a student has to score at least 60 out of a total of 100+ points. The points can be scored for:

  • a presentation during the excercise classes: up to 50 points
  • questions asked during other people's presentations: up to 1 point per question
  • a written exam at the end of the semester: up to 50 points

The final grade is calculated as follows (where the points for questions need not contribute linearly to the aggregate points):

Points 0-51 52-59 60-67 68-75 76-83 84-91 92-...
Grade 2 (fail) 2+ (fail) 3 3+ 4 4.5 5

Presentation Rules

A presentation is normally given in Polish with slides in English. However, if foregin students enroll for the course, all presentations will be required to be given in English. The strict time limit of a single talk is 60 minutes, in case of one presentation per class, or 30 minutes, if there are two presentations during a single class. The presenting student will be interrupted after this period. During the talk, other students are discouraged from asking questions. After the talk, there is a 15-30-minute questions-and-answers session, during which the presenter answers question posed by the lecturer and other students. The objective of the questions could be, for instance, to clarify some aspects of the paper or to learn the presenter's opinion on a problem related to the paper.

During his/her presentation of a paper, a student is obliged to display PowerPoint/PDF slides for the paper. As a reminder, they have to be in English. The student has to prepare the slides on his/her own. If some slides for the paper already exist on the Internet, the concents of those slides can be re-used by the student preparing his/her own slides only if re-using the contents does not violate any copyrights, especially when the student's presentation is made available online. Moreover, the student has to acknowledge using somebody else's slides.

Tips:

  • Read your paper well in advance to understand it and to later be able to answer other students' questions.
  • Practice your talk to fit in the time limit.
  • Try to briefly go over the related work cited in the paper as this can give you some valuable input on the problem the paper is solving.
  • Try to find any follow-ups on the paper because this can be rewarding as well. Skimming through follow-up papers will help you better understand the topic.
  • Ask the presenter questions that, rather than proving the presenter doesn't know something, lead to interesting discussions. You are not awarded points for mean or stupid questions.
  • If you have read and understood the presented paper, and if you have practiced your talk, relax during your presentation: you will surely be able to answer all questions.

Exam Rules

The exact rules will be given later. In summary, the exam will cover the lecture topics as well as some issues raised during the student presentations. However, this year the exam will be yet again different than in the past years.

Lecture Topics and Schedule

Since this is still a developing course, this year's lectures will be given mostly based on a book by my PhD adviser and the head of my former research group: Maarten van Steen and Andrew S. Tanenbaum, “Distributed Systems: Principles and Paradigms,” Second Edition, Prentice Hall, 2007, 702 pages, ISBN 9780132392273. Purchasing the book is not mandatory as the lecture slides will be available here.

Date Topics Slides
October 3, 2012 Introduction:
goals of distributed systems, common types of distributed systems
lecture 01
October 10, 2012 Architectures:
architectural styles, system architectures, self-management
lecture 02
October 17, 2012 Processes:
threads, virtualization, clients & servers, server clusters, code migration
lecture 03
October 24, 2012 Communication:
fundamentals, remote procedure call, message-oriented communication, stream-oriented communication, multicast communication
lecture 04-05
October 31, 2012
November 7, 2012 Naming:
basic terms and definitions, flat naming, structured naming, attribute-based naming
lecture 06-07
and
supplement
November 14, 2012
November 21, 2012 Synchronization:
clock synchronization, logical clocks, totally-ordered multicast, causally-ordered multicast mutual exclusion, global positioning of nodes, leader election
lecture 08-09
and
supplement
November 28, 2012
December 5, 2012 Consistency and Replication:
continuous consistency, data-centric and client-centric consistency models, replica management, consistency protocols
lecture 10-11
December 12, 2012
December 19, 2012 Fault Tolerance:
failure models, failure masking, failure detection, reliable client-server communication, atomic multicast, two-phase commit, three-phase commit, checkpointing, logging, recovery, agreement in faulty systems, Paxos
lecture 12-14
and
supplement
January 9, 2013
January 16, 2013
January 23, 2013 Security:
policies and mechanisms, secure channels, secure group communication
lecture 15

Presentation Topics

The papers to be presented by students during the practical work classes are listed below. They have been chosen based on their age and educational value (in the prejudiced opinion of the lecturer). The papers are available for download from the university computers. Should you have problems accessing them, please contact the lecturer.

  1. A. Adya, G. Cooper, D. Myers, and M. Piatek: “Thialfi: A Client Notification Service for Internet-Scale Applications,” in Proceedings ACM SOSP 2011.
  2. M. Balakrishnan, D. Malkhi, V. Prabhakaran, T. Wobber, M. Wei, and J.D. Davis: “CORFU: A Shared Log Design for Flash Clusters,” in Proceedings USENIX NDSI 2012.
  3. R. Balan, N. Khoa, and J. Lingxiao: “Real-Time Trip Information Service for a Large Taxi Fleet,” in Proceedings ACM MobiSys 2011.
  4. Beaver, D., Kumar, S., Li, H.C., Sobel, J., and Vajgel, P.: “Finding a Needle in Haystack: Facebook's Photo Storage,” in Proceedings USENIX OSDI 2010.
  5. J. Biagioni, T. Gerlich, T. Merrifield, and J. Eriksson: “EasyTracker: Automatic Transit Tracking, Mapping, and Arrival Time Prediction Using Smartphones,” in Proceedings ACM SenSys 2011.
  6. Q. Cao, M. Sirivianos, X. Yang, and T. Pregueiro: “Aiding the Detection of Fake Accounts in Large Scale Social Online Services,” in Proceedings USENIX NSDI 2012.
  7. B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie, Y. Xu, S. Srivastav, J. Wu, H. Simitci, J. Haridas, C. Uddaraju, H. Khatri, A. Edwards, V. Bedekar, S. Mainali, R. Abbasi, A. Agarwal, M.F. ul Haq, M. I. ul Haq, D. Bhardwaj, S. Dayanand, A. Adusumilli, M. McNett, S. Sankaran, K. Manivannan, and L. Rigas: “Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency ,” in Proceedings ACM SOSP 2011.
  8. Y. Chen, K. Srinivasan, G. Goodson, and R. Katz: “Design Implications for Enterprise Storage Systems via Multi-Dimensional Trace Analysis,” in Proceedings ACM SOSP 2011.
  9. R. Cheng, J. Hong, A. Kyrola, Y. Miao, X. Weng, M. Wu, F. Yang, L. Zhou, F. Zhao, and E. Chen: “Kineograph: Taking the Pulse of a Fast-Changing and Connected World,” in Proceedings ACM EuroSys 2012.
  10. E. Cheslack-Postava, T. Azim, B.F.T. Mistree, and D.R. Horn, J. Terrace, P. Levis, and M.J. Freedman: “A Scalable Server for 3D Metaverses,” in Proceedings USENIX ATC 2012.
  11. P. Costa, A. Donnelly, A. Rowstron, and G. O'Shea: “Camdoop: Exploiting In-network Aggregation for Big Data Applications,” in Proceedings USENIX NSDI 2012.
  12. DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., and Vogels, W.: “Dynamo: Amazon's highly available key-value store,” in Proceedings ACM SOSP 2007.
  13. P. Gilbert, J. Jung, K. Lee, H. Qin, D. Sharkey, A. Sheth, and L.P. Cox: “YouProve: Authenticity and Fidelity in Mobile Sensing,” in Proceedings ACM SenSys 2011.
  14. L. Glendenning, I. Beschastnikh, A. Krishnamurthy, and T. Anderson: “Scalable Consistency in Scatter,” in Proceedings ACM SOSP 2011.
  15. T. Harter, C. Dragga, M. Vaughn, A.C. Arpaci-Dusseau, and R.H. Arpaci-Dusseau: “A File is Not a File: Understanding the I/O Behavior of Apple Desktop Applications,” in Proceedings ACM SOSP 2011.
  16. S. Kato, M. McThrow, C. Maltzahn, and S. Brandt: “Gdev: First-Class GPU Resource Management in the Operating System,” in Proceedings USENIX ATC 2012.
  17. M. Kj√¶rgaard, S. Bhattacharya, H. Blunck, and P. Nurmi: “Energy-efficient Trajectory Tracking for Mobile Devices,” in Proceedings ACM MobiSys 2011.
  18. E. Koukoumidis, L. Peh, and M. Martonosi: “SignalGuru: Leveraging Mobile Phones for Collaborative Traffic Signal Schedule Advisory,” in Proceedings ACM MobiSys 2011.
  19. H. Lim, B. Fan, D.G. Andersen, and M. Kaminsky: “SILT: A Memory-Efficient, High-Performance Key-Value Store,” in Proceedings ACM SOSP 2011.
  20. W. Lloyd, M.J. Freedman, M. Kaminsky, D.G. Andersen: “Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS,” in Proceedings ACM SOSP 2011.
  21. M. Mesnier, J.B. Akers, F. Chen, and T. Luo: “Differentiated Storage Services,” in Proceedings ACM SOSP 2011.
  22. N.P. Nguyen, T.N. Dinh, S. Tokala, and M.T. Thai: “Overlapping Communities in Dynamic Networks: Their Detection and how they can help Mobile Applications,” in Proceedings ACM MobiCom 2011.
  23. D. Ongaro, S.M. Rumble, R. Stutsman, J. Ousterhout, and M. Rosenblum: “Fast Crash Recovery in RAMCloud,” in Proceedings ACM SOSP 2011.
  24. R.A. Popa, C.M.S. Redfield, N. Zeldovich, and H. Balakrishnan: “CryptDB: Protecting Confidentiality with Encrypted Query Processing,” in Proceedings ACM SOSP 2011.
  25. C. Qin, X. Bao, R. Choudhury, S. Nelakuditi: “TagSense: A Smartphone-based Approach to Automatic Image Ta,” in Proceedings ACM MobiSys 2011.
  26. M. Ra, A. Sheth, L. Mummert, P. Pillai, D. Wetherall, and R. Govindan: “Odessa: Enabling Interactive Perception Applications on Mobile Devices,” in Proceedings ACM MobiSys 2011.
  27. K.K. Rachuri, C. Mascolo, M. Musolesi, and P.J. Rentfrow: “SociableSense: Exploring the Trade-offs of Adaptive Sampling and Computation Offloading for Social Sensing,” in Proceedings ACM MobiCom 2011.
  28. van Renesse, R., Birman, K.P., and Vogels, W.: “Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining,” ACM Transactions on Computer Systems, vol. 21, no. 2, May 2003.
  29. Ch.J. Rossbach, J. Currey, M. Silberstein, B. Ray, and E. Witchel: “PTask: Operating System Abstractions To Manage GPUs as Compute Devices,” in Proceedings ACM SOSP 2011.
  30. S. Sen, J.R. Lorch, R. Hughes, C. Garcia Jurado Suarez, B. Zill, W. Cordeiro, and J. Padhye: “Don't Lose Sleep Over Availability: The GreenUp Decentralized Wakeup Service,” in Proceedings USENIX NSDI 2012.
  31. H. Shin, Y. Chon, K. Park, and H. Cha: “Finding MiMo: Tracing a Missing Mobile Phone using Daily Observations,” in Proceedings ACM MobiSys 2011.
  32. Y. Sovran, R. Power, M.K. Aguilera, and J. Li: “Transactional storage for geo-replicated systems,” in Proceedings ACM SOSP 2011.
  33. C.-L. Tsao, S. Kakumanu, and R. Sivakumar: “SmartVNC: An Effective Remote Computing Solution for Smartphones,” in Proceedings ACM MobiCom 2011.
  34. B. Viswanath, M. Mondal, and K. Gummadi, A. Mislove, and A. Post: “Canal: Scaling social network-based Sybil tolerance schemes,” in Proceedings ACM EuroSys 2012.
  35. M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M.J. Franklin, S. Shenker, and I. Stoica: “Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing,” in Proceedings USENIX NSDI 2012.
  36. J.C. Corbett, J. Dean, M. Epstein, A. Fikes, Ch. Frost, J.J. Furman, S. Ghemawat, A. Gubarev, Ch. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, Ch. Taylor, R. Wang, and D. Woodford: “Spanner: Google's Globally-Distributed Database,” in Proceedings USENIX OSDI 2012.

For his/her own presentation, a student can also propose a paper not present in the above list. Such a paper, however, has to be accepted earlier by the lecturer.

Presentation Schedule

Monday Class

Date Presenter(s) Theme Paper(s)
October 1, 2012 Canceled
October 8, 2012 K. Iwanicki Introduction 28: “Astrolabe: ...”
October 15, 2012 T. Wysocki Cloud computing 4: “Finding ...”
October 22, 2012 A. Findeisen
M. Gregorczyk
Cloud computing 19: “SILT: ...”
23: “Fast crash ...”
October 29, 2012 K. Nienaltowski Cloud computing 1: “Thialfi: ...”
November 5, 2012 M. Grabowski
K. Gogolewski
Social networks 27: “SociableSense: ...”
22: “Overlapping Communities...”
November 12, 2012 M. Sabacinski Cloud computing 7: “Windows Azure ...”
November 19, 2012 M. Smiech
W. Zoltak
Cloud computing 20: “Don't settle ...”
32: “Transactional storage ...”
November 26, 2012 Canceled (Dean's hours)
December 3, 2012 Z. Chlebicki
M. Ptaszynski
Cloud computing 35: “Resilient distributed ...”
11: “Camdoop: ...”
December 10, 2012 G. Milka Ubiquitous computing 26: “Odessa: ...”
December 17, 2012 K. Krolak Ubiquitous computing 3: “Real-time ...”
January 7, 2013 T. Pazurkiewicz Cloud computing 10: “... metaverses ...”
January 14, 2013 M. Koscielnicki Cloud computing 16: “Gdev: ...”
January 21, 2013 K. Baranowska Cloud computing 24: “CryptDB: ...”

Wednesday Class

Date Presenter(s) Theme Paper(s)
October 3, 2012 K. Iwanicki Introduction 28: “Astrolabe: ...”
October 10, 2012 M. Oniszczuk Cloud computing 12: “Dynamo: ...”
October 17, 2012 M. Osowski Cloud computing 14: “Scalable consistency ...”
October 24, 2012 P. Dobrowolski
Sz. Bachnij
Cloud computing 8: “Design implications ...”
21: “Differentiated storage ...”
October 31, 2012 G. Jablonski Ubiquitous computing 25: “TagSense: ...”
November 7, 2012 L. Piatkowski Ubiquitous computing 31: “Finding MiMo: ...”
November 14, 2012 M. Szczepaniak
M. Czerski
Cloud computing 15: “A file is not ...”
2: “CORFU: ...”
November 21, 2012 T. Falkiewicz Ubiquitous computing 33: “SmartVNC: ...”
November 28, 2012 P. Posielezny Ubiquitous computing 18: “SignalGuru: ...”
December 5, 2012 K. Wisniewski
R. Hryciuk
Ubiquitous computing 17: “Energy-efficient ...”
5: “EasyTracker: ...”
December 12, 2012 A. Karczmarz Cloud computing 29: “PTask: ...”
December 19, 2012 R. Burny
K. Yurtsever
Cloud computing 9: “Kineograph: ...”
30: “Don't lose ...”
January 9, 2013 S. Khanin Ubiquitous computing 13: “YouProve: ...”
January 16, 2013 M. Pecio Cloud computing 36: “Spanner: ...”
January 23, 2013 R. Pohnke Social networks 34: “Canal: ...”

Past Exams

Below, you can find the questions from past exams:

Year Exam Set Participants Points
Course Exam % Available Min Avg Med Max
2012/2013 Final (test) 34 34 100 25 3 10.33 10 22
2011/2012 Final 36 34 94.4 50 10 29.85 30.5 49
2010/2011 Part II 26 21 80.8 25 3.75 16.27 13.5 24.25
2010/2011 Late Part I 26 11 42.3 25 13.75 21.6 21.25 24.75
2010/2011 Early Part I 26 17 65.4 25 9.25 14.9 13.5 22