Advanced Distributed Systems
Course: Advanced Distributed Systems (320571)
Instructor: Jürgen Schönwälder
TA: Anuj Sehgal
Thursday 14:15 - 15:30 West Hall 6
Friday 14:15 - 15:30 West Hall 6
Start: September 1st, 2011

This course discusses the operational and management aspects of distributed systems (including networked systems) and the security aspects of distributed systems (authentication, privacy, key creation and distribution protocols, firewalls, access control models, trust in distributed systems). In addition, this course will cover recent approaches to build self-controlling and self-organizing distributed systems.

This course assumes that students are familiar with fundamental distributed systems concepts usually covered in undergraduate courses on distributed systems. The course will be accompanied by a hands-on a Advanced Distributed Systems Lab, where selected topics of the course will be implemented.

Course Materials:

This course does not follow a text book. Most of the material discussed in the course is taken from recent research papers. Students are expected to obtain and read original research papers:

  • E. Cohen and S. Shenker: Replication Strategies in Unstructured Peer-to-Peer Networks. Proc. SIGCOMM 2002, ACM, Pittsburgh, August 2002.
  • S. Saroiu and P. Gummadi and S. Gribble: A Measurement Study of Peer-to-Peer File Sharing Systems. Proc. of Multimedia Computing and Networking (MMCN 2002), January 2002.
  • K.P. Gummadi and R.J. Dunn and S. Saroiu and S.D. Gribble and H.M. Levy and J. Zahorjan: Measurement, Modeling, and Analysis of a Peer-to-Peer File-sharing Workload. Proc. of the 19th ACM Symposium on Operating Systems Principles (SOSP 2003), ACM, January 2003.
  • I. Stoica and R. Morris and D. Karger and M. F. Kaashoek and H. Balakrishna: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. Proc. SIGCOMM 2001, ACM, San Diego, August 2001.
  • S. Ratnasamy and P. Francis and M. Handley and R. Karp and S. Shenker: A Scalable Content-Addressable Network. Proc. SIGCOMM 2001, ACM, San Diego, August 2001.
  • A. Rowstron and P. Druschel: Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. Proc. 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), Heidelberg, November 2001.
  • S. Androutsellis-Theotokis and D. Spinellis: A Survey of Peer-to-Peer Content Distribution Technologies. ACM Computing Surveys 7(2), 2005.
  • S. Rhea and B. Godfrey and B. Karp and J. Kubiatowicz and S. Ratnasamy and S. Shenker and I. Stoica and H. Yu: OpenDHT: A Public DHT Service and Its Uses. Proc. SIGCOMM 2005, ACM, Philadelphia, August 2005.
  • Y. Chawathe and S. Ramabhadran and S. Ratnasamy and A. LaMarca and S. Shenker and J. Hellerstein: A Case Study in Building Layered DHT Applications. Proc. SIGCOMM 2005, ACM, Philadelphia, August 2005.
  • J. Risson and T. Moors: Survey of Research towards Robust Peer-to-Peer Networks: Search Methods. Computer Networks 50(17), Elsevier, December 2006.
  • L. Gong: JXTA: A Network Programming Environment. IEEE Internet Computing, 5(3), May 2001.
  • D. Qiu and R. Srikant: Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks. Proc. SIGCOMM 2004, ACM, Portland, September 2004.
  • L. Guo and S. Chen and Z. Xiao and E. Tan and X. Ding and X. Zhang: A Performance Study of BitTorrent-like Peer-to-Peer Systems. IEEE Journal on Selected Areas in Communications, 25(1), January 2007.
  • T. Locher and P. Moor and S. Schmid and R. Wattenhofer: Free Riding in BitTorrent is Cheap. Proc. of the 5th Workshop on Hot Topics in Networks, ACM, Irvine, November 2006.
  • R. Dingledine and N. Mathewson and P. Syverson: Tor: The Second-Generation Onion Router. Proc. of the 13th USENIX Security Symposium, San Diego, August 2004.
  • S.J. Murdoch: Hot or Not: Revealing Hidden Services by their Clock Skew. Proc. of the 13th ACM Conference on Computer and Communications Security (CCS'06), ACM, Alexandria, November 2006.
  • D. Gay and P. Levis and R. von Behren and M. Welsh and E. Brewer and D. Culler: The nesC Language: A Holistic Approach to Networked Embedded Systems. Proc. of the ACM Conference on Programming Language Design and Implementation (PLDI03), ACM, June 2003.
  • J.E. Elson: Time Synchronization in Wireless Sensor Networks. PhD Thesis, University of California Los Angeles, 2003.
  • K. Roemer: Time Synchronization and Localization in Sensor Networks. PhD Thesis, ETH Zurich, 2005.
  • G. Werner-Allen and G. Tewari and A. Patel and M. Welsh and R. Nagpal: Firefly-Inspired Sensor Network Synchronicity with Realistic Radio Effects. Proc. of the ACM Conference on Embedded Networked Sensor Systems (SenSys'05), ACM, November 2005.
  • S.R. Madden and M.J. Franklin and J.M. Hellerstein and W. Hong: TinyDB: An Acquisitional Query Processing System for Sensor Networks. ACM Transactions on Database Systems, 30(1), ACM, March 2005.
2011-09-01 2011-09-02 Introduction, Wireless Sensor Networks
2011-09-08 2011-09-09 IEEE 802.15.4, 6LoWPAN, RPL, COAP
2011-09-15 2011-09-16 Distributed Algorithms, Events, Causality
2011-09-22 2011-09-23 Snapshots and Mutual Exclusion
2011-09-29 2011-09-30 Wave and Traversal Algorithms
2011-10-06 2011-10-07 Election Algorithms and Broadcasts
2011-10-13 2011-10-14 TinyDB, Distributed Data Aggregation
2011-10-20 2011-10-21 Unstructured P2P Networks
2011-10-27 2011-10-28 Structured P2P Networks
2011-11-03 2011-11-04 P2P Security and Anonymity
2011-11-10 2011-11-11 Virtualization
2011-11-17 2011-11-18 Cloud Computing: Infrastructure as a Service
2011-11-24 2011-11-25 Distributed Storage
2011-12-01 2011-12-02 Cloud Computing: Platform as a Service

The final grade is made up of the final exam (40 %), biweekly quizzes (30 %) and some homework assignments (30 %). It is required to submit the solution for homeworks assignments electronically. Homeworks may need to be defended in an oral interview. Late submissions after the deadline will be penalized. For every hour late, you will loose 10% of the points. We account an additional bonus of 15 minutes for electronic submissions (you know how well email sometimes works). This means, a solution received 01:15 late will loose 10%, a solution received 02:15 late will loose 20% and so on. If we receive more than one submission, we will pick the last one.

Any programs which have to be written will be evaluated based on the following criteria:

  • correctness including proper handling of error conditions
  • proper use of programming language constructs
  • clarity of the program organization and design
  • readability of the source code and any output produced

Source code must be accompanied with a README providing an overview of the source files and giving instructions how to build the programs. A suitable Makefile is required if the build process involves more than a single source file.

The policy on makeup quizzes and exams is the following: To be able to get a makeup, you have to either (a) have an official excuse from the registrar's office or (b) approach me well in advance of the quiz/exam with a very good reason for not being able to participate (e.g., because you take a GRE computer science subject test at the day of a quiz). Furthermore, I require that people take action to immediately contact me when they return to campus so that we can fix a date for the makeup. Once a week has passed, I do not feel obliged to offer a makeup anymore.

2011-09-15 Assignment #1 6LoWPAN, trickle algorithm
2011-10-10 Assignment #2 wave algorithms, distributed depth-first-search
2011-12-02 Assignment #3 peer-to-peer systems
2011-09-23 Quiz #1 events, causality, clocks, snapshots
2011-10-07 Quiz #2 waves, traversals, elections
2011-11-25 Quiz #3 virtualization
  • Final Exam (December 15th, oral exam)