Distributed Systems Course (fall 2012/2013)

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