Distributed Systems Course (fall 2011/2012)

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: Friday, February 3, 12:30 PM - 2:30 PM, Room 2180

This (second) 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 45 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-45-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.


  • 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, it will be a bit different than the last year.

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 5, 2011 Introduction:
goals of distributed systems, common types of distributed systems
lecture 01
October 12, 2011 Architectures:
architectural styles, system architectures, self-management
lecture 02
October 19, 2011 Processes:
threads, virtualization, clients & servers, code migration
lecture 03
October 26, 2011 Communication:
fundamentals, remote procedure call, message-oriented communication, stream-oriented communication, multicast communication
lecture 04-05
November 2, 2011
November 9, 2011 Naming:
basic terms and definitions, flat naming, structured naming, attribute-based naming
lecture 06-07
November 16, 2011
November 23, 2011 Synchronization:
clock synchronization, logical clocks, totally-ordered multicast, causally-ordered multicast mutual exclusion, global positioning of nodes, leader election
lecture 08-09
November 30, 2011
December 7, 2011 Consistency and Replication:
data-centric and client-centric consistency models, replica management, consistency protocols
lecture 10-11
December 14, 2011
December 21, 2011 Fault Tolerance:
failure models, failure masking, failure detection, reliable client-server communication, agreement in faulty systems, atomic multicast, two-phase commit, three-phase commit, checkpointing, logging, recovery
lecture 12-13
January 4, 2012
January 11, 2012 Security:
policies and mechanisms, secure channels, secure group communication, access control, fire walls, key management, secure group management, delegation
lecture 14-15
January 18, 2012

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. Alvaro, P., Condie, T., Conway, N., Elmeleegy, K., Hellerstein, J.M., and Sears, R.: “BOOM Analytics: Exploring Data-Centric, Declarative Programming for the Cloud,” in Proceedings ACM EuroSys 2010.
  2. Ananthanarayanan, G., Agarwal, S., Kandula, S., Greenberg, A., Stoica, I., Harlan, D., and Harris, E.: “Scarlett: Coping with Skewed Content Popularity in MapReduce Clusters,” in Proceedings ACM EuroSys 2011.
  3. Ananthanarayanan, G., Kandula, S., Greenberg, A., Stoica, I., Lu, Y., Saha, B., and Harris, E.: “Reining in the Outliers in Map-Reduce Clusters using Mantri,” in Proceedings USENIX OSDI 2010.
  4. Azizyan, M., Constandache, I., and Choudhury, R.R.: “SurroundSense: Mobile phone localization via ambience fingerprinting,” in Proceedings ACM MobiCom 2009.
  5. Bailey, K., Ceze, L., Gribble, S.D., and Levy, H.M.: “Operating System Implications of Fast, Cheap, Non-Volatile Memory,” in Proceedings USENIX HotOS 2011.
  6. 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.
  7. Chawla, A., Reed, B., Juhnke, K., and Syed, G.: “Semantics of Caching with SPOCA: A Stateless, Proportional, Optimally-Consistent Addressing Algorithm,” in Proceedings USENIX ATC 2011.
  8. Chen, S., Chen, H., and Caballero, M.: “Residue Objects: A Challenge to Web Browser Security,” in Proceedings ACM EuroSys 2010.
  9. Chintalapudi, K., Iyer, A.P., Padmanabhan, V.N.: “Indoor Localization without the Pain,” in Proceedings ACM MobiCom 2010.
  10. Chun, B.-G., Ihm, S., Maniatis, P., Naik, M., and Patti, A.: “CloneCloud: Elastic Execution Between Mobile Device and Cloud,” in Proceedings ACM EuroSys 2011.
  11. Constandache, I., Bao, X., Azizyan, M., and Choudhury, R.R.: “Did you see Bob?: human localization using mobile phones,” in Proceedings ACM MobiCom 2010.
  12. Cozzie, A., Finnicum, M., and King, S.T.: “Macho: Programming with Man Pages,” in Proceedings USENIX HotOS 2011.
  13. 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.
  14. Enck, W., Gilbert, P., Chun, B.-g., Cox, L.P., Jung, J., McDaniel, P., Sheth, A.N.: “TaintDroid: An Information-Flow Tracking System for Realtime Privacy Monitoring on Smartphones,” in Proceedings USENIX OSDI 2010.
  15. Fetterly, D., Haridasan, M., Isard, M., and Sundararaman, S.: “TidyFS: A Simple and Small Distributed File System,” in Proceedings USENIX ATC 2011.
  16. Ford, D., Labelle, F., Popovici, F.I., Stokely, M., Truong, V.-A., Barroso, L., Grimes, C., and Quinlan, S.: “Availability in Globally Distributed Storage Systems,” in Proceedings USENIX OSDI 2010.
  17. Geambasu, R., John, J.P., Gribble, S.D., Kohno, T., and Levy, H.M.: “Keypad: An Auditing File System for Theft-Prone Devices,” in Proceedings ACM EuroSys 2011.
  18. Haridasan, M., Mohomed, I., Terry, D., Thekkath, C.A., and Zhang, L.: “StarTrack Next Generation: A Scalable Infrastructure for Track-Based Applications,” in Proceedings USENIX OSDI 2010.
  19. Holland, D.A. and Seltzer, M.I.: “Multicore OSes: Looking Forward from 1991, er, 2011,” in Proceedings USENIX HotOS 2011.
  20. Iu, M.-Y. and Zwaenepoel, W.: “HadoopToSQL: A Map-Reduce Query Optimizer,” in Proceedings ACM EuroSys 2010.
  21. Levis, P., Patel, N., Culler, D., and Shenker, S.: “Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks,” in Proceedings USENIX NSDI 2004.
  22. Meyerowitz, J.T. and Choudhury, R.R.: : “Hiding stars with fireworks: Location privacy through camouflage,” in Proceedings ACM MobiCom 2009.
  23. Ni, S.-Y., Tseng, Y.-C., Chen, Y.-S., and Sheu, J.-P.: “The broadcast storm problem in a mobile ad hoc network,” in Proceedings ACM MobiComm 1999.
  24. Nightingale, E.B., Douceur, J.R., and Orgovan, V.: “Cycles, Cells and Platters: An empirical analysis of hardware failures on a million consumer PCs,” in Proceedings ACM EuroSys 2011.
  25. Pathak, A., Hu, Y.C., Zhang, M., Bahl, V., and Wang, Y.-M.: “Fine-Grained Power Modeling for Smartphones Using System Call Tracing,” in Proceedings ACM EuroSys 2011.
  26. Pitsillidis, A., Xie, Y., Yu, F., Abadi, M., Voelker, G.M., and Savage, S.: “How to Tell an Airport from a Home: Techniques and Applications,” in Proceedings ACM HotNets 2010.
  27. Popa, L., Ghodsi, A., and Stoica, I.: “HTTP as the Narrow Waist of the Future Internet,” in Proceedings ACM HotNets 2010.
  28. Post, A., Navarro, J., Kuznetsov, P., and Druschel, P.: “Autonomous Storage Management for Personal Devices with PodBase,” in Proceedings USENIX ATC 2011.
  29. 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.
  30. Roy, A., Rumble, S.M., Stutsman, R., Levis, P., Mazières, D., and Zeldovich, N.: “Energy Management in Mobile Devices with the Cinder Operating System,” in Proceedings ACM EuroSys 2011.
  31. Strauss, J., Paluska, J.M., Lesniewski-Laas, C., Ford, B., Morris, R., and Kaashoek, F.: “Eyo: Device-Transparent Personal Storage,” in Proceedings USENIX ATC 2011.
  32. Vasudevan, V. and Andersen, D.G.: “The Case for VOS: The Vector Operating System,” in Proceedings USENIX HotOS 2011.
  33. Wobber, T., Rodeheffer, T.L., and Terry, D.B.: “Policy-based Access Control for Weakly Consistent Replication,” in Proceedings ACM EuroSys 2010.
  34. Baset, S.A. and Schulzrinne, H.G.: “An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol,” in Proceedings IEEE INFOCOM 2006.
  35. Terry, D.B., Theimer, M.M., Petersen, K., Demers, A.J., Spreitzer, M.J., and Hauser, C.H.: “Managing update conflicts in Bayou, a weakly consistent replicated storage system,” in Proceedings ACM SOSP 1995.
  36. Hull, B., Bychkovsky, V., Zhang, Y., Chen, K., Goraczko, M., Miu, A., Shih, E., Balakrishnan, H., and Madden, S.: “CarTel: A Distributed Mobile Sensor Computing System,” in Proceedings ACM SenSys 2006.
  37. Zhuang, L., Zhou, F., Zhao, B.Y., and Rowstron, A.: “Cashmere: Resilient Anonymous Routing,” in Proceedings USENIX NSDI 2005.
  38. Multiple sources: “Cassandra,”.
  39. Yip, A., Narula, N., Krohn, M., and Morris, R.: “Privacy-preserving browser-side scripting with BFlow,” in Proceedings ACM EuroSys 2009.
  40. Seltzer, M. and Murphy, N.: “Hierarchical File Systems are Dead,” in Proceedings USENIX HotOS 2009.

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 3, 2011 K. Iwanicki Introduction 29: “Astrolabe: ...”
October 10, 2011 J. Bartodziej Clouds: Practice 13: “Dynamo: ...”
October 17, 2011 P. Glazar
L. Chodarcewicz
Mobility: Broadcast 23: “The broadcast storm ...”
21: “Trickle: ...”
October 24, 2011 P. Przytula Mobility: Localization 11: “Did you see ...”
October 31, 2011 No class
November 7, 2011 P. Karasinski Mobility & Clouds 10: “CloneCloud: ...”
November 14, 2011 P. Posielezny Clouds: Performance 2: “Scarlett: ...”
November 21, 2011 K. Wychowaniec Clouds: Performance 20: “HadoopToSQL: ...”
November 28, 2011 B. Kulabinski
M. Lopatka
Earlier work for
the enrolled late
34: “An Analysis ...”
38: “Cassandra”
December 5, 2011 J. Kopczewski Clouds: Fault Tolerance 3: “Reining in ...”
December 12, 2011 R. Rawicki Clouds: Fault tolerance 24: “Cycles, Cells, ...”
December 19, 2011 R. Kozikowski Clouds: Fault tolerance 16: “Availability in ...”
January 2, 2012 M. Dzwonek
K. Pawlowski
Mobility: Security 17: “KeyPad: ...”
14: “TaintDroid: ...”
January 9, 2012 R. Rosolek
A. Skalski
Security 8: “Residue Objects: ...”
37: “Cashmere: ...”
January 16, 2011 A. Morawski
M. Wlodarczyk
Provocative ideas 5: “Operating system ...”
40: “Hierarchical File ...”

Wednesday Class

Date Presenter(s) Theme Paper(s)
October 5, 2011 K. Iwanicki Introduction 29: “Astrolabe: ...”
October 12, 2011 P. Spodymek Clouds: Practice 6: “Finding ...”
October 19, 2011 A. Przedniczek
P. Wojciechowski
Mobility: Localization 9: “Indoor localization ...”
4: “SurroundSense ...”
October 26, 2011 M. Klimek Mobility: Localization 18: “StarTrack Next ...”
November 2, 2011 R. Chojnacka Mobility: Security 22: “Hiding stars ...”
November 9, 2011 D. Borowiec Clouds: Performance 15: “TidyFS: ...”
November 16, 2011 P. Skowron Clouds: Performance 7: “Semantics of ...”
November 23, 2011 M. Michalowski Mobility: Energy 30: “Energy Management ...”
November 30, 2011 D. Rodziewicz Mobility: Energy 25: “Fine-grained ...”
December 7, 2011 D. Rajin Earlier work for
the enrolled late
36: “CarTel: ...”
December 14, 2011 R. Bereski
T. Kleczek
Mobility: Storage 31: “Eyo: Device-Transparent ...”
28: “Autonomous storage ...”
December 21, 2011 J. Kanska
J. Kudelka
Various topics 1: “BOOM Analytics: ...”
39: “Privacy-preserving ...”
January 4, 2012 M. Kawiak Security 33: “Policy-based ...”
January 11, 2012 G. Swatowski
P. Leszczynski
Provocative ideas 26: “How to tell ...”
27: “HTTP as the Narrow ...”
January 18, 2011 P. Hajdan
M. Weksej
Provocative ideas 19: “Multicore OSes ...”
32: “The case for VOS: ...”

Past Exams

Below, you can find the questions from past exams:

Year Exam Set Participants Points
Course Exam % Available Min Avg Med Max
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