Fall 2003 - CS 553 (Call no 35366) Distributed Systems

Textbooks

• (main text) Advanced Concepts in Operating Systems by Singhal and Shivaratri, McGraw Hill, 1994
• Selected papers and other material from the literature will be posted on the web or distributed in class.
• Additional reference texts
  • Distributed Systems, by Sape Mullender, Addison-Wesley, 1993
  • Distributed Operating Systems and Algorithms, by Chow and Johnson, Addison-Wesley, 1997.
  • Distributed Systems Concepts and Design, by Coulouris, Dollimore, and Kindberg, Addison-Wesley, 2001.

Course Description

1. Models: synchronous/asynchronous; shared memory/message-passing
2. Global states and snapshots; time models
3. Group communication, managing group views
4. State predicates
5. Mutual exclusion, deadlock detection, leader election
6. Distributed shared memory - coherence, models
7. Checkpointing, rollback recovery; distributed debugging
8. Agreement and consensus
9. Peer-to-peer computing
10. Multicast
11. other current topics

Grading

• Term paper (25%); topic of your choice
  [12% for original research content; 7% for breadth and depth of literature survey; 6% for organization and presentation]
• Class presentation, critiques, & attendance of other presentations (15%)
• Test 1 (30%). All or a part of this test may be take-home (depending on class-size).
• Test 2 (30%). All or a part of this test may be take-home (depending on class size).

Prerequisites

TENTATIVE course progress chart:

• Week 1.1: Introduction, models
• Week 1.2: models, failure models, synchronous/asynchronous, blocking/nonblocking communication
• Week 2.1: elementary algorithms
• Week 2.2: Global states; Chandy-Lamport algorithm; read this survey.
• Week 3.1: time - scalar and vector clocks; partial orders; clock synchronization
• Week 3.2: predicates - possibly and definitely; detection algos
• Week 4.1: Causal order; total order
  
• Week 4.2: fault-tolerant protocols; layered protocol design
• Week 5.1: termination detection; message-passing mutual exclusion
• Week 5.2: message-passing mutual exclusion
• Week 6.1: message-passing mutual exclusion
• Week 6.2: agreement and consensus
• Week 7.1: Test 1 (October 7) in SES 230.
• Week 7.2: agreement and consensus
• Week 8.1: agreement and consensus
• Week 8.2: Distributed shared memory
• Week 9.1: Distributed shared memory
• Week 9.2: load balancing; fault-tolerance
• Week 10.1: fault-tolerance
• Week 10.2: checkpointing and rollback recovery
• Week 11.1: checkpointing and rollback recovery. Take-home test will be distributed.
• Week 11.2: In-class Test 2 (November 6) in SES 230. ; also Take-home test due
• Week 12.1 (Nov 11): Presentation 2 by US,PS: Coordinated placement and replacement for large-scale distributed caches, Korupolu, M.R.; Dahlin, M., Page(s): 1317- 1329, IEEE TKDE, Nov/Dec. 2002.
• Week 12.2 (Nov 13): Presentation 3 by AB,MB: Chord: a scalable peer-to-peer lookup protocol for internet applications. Ion Stoica, Robert Morris, David Liben-Nowell, David Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan, IEEE/ACM Transactions on Networking 11(1): 17-32 (2003)
• Week 13.1 (Nov 18): Presentation 4 by SK,AS: A Scalable Content-Addressable Network, Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker, ACM SIGCOMM 2001.
• Week 13.15 (Nov 19, 8:00am - 9:15am in SEO 1000): Presentation 1 by JS,AW: Internet Time Synchronization: the Network Time Protocol, D. Mills. IEEE Trans. on Communications, 39(10): 1482-1493, Oct 1991.
• Week 13.2 (Nov 20): Presentation 5 by WK,MS: Deno: Decentralized p2p object replication system for weakly connected environments, Cetintemel, U.; Keleher, P.J.; Bhattacharjee, B.; Franklin, M.J., IEEE Transactions on Computers, 52(7), July 2003, pages 943-959.
• Week 14.1 (Nov 25): Presentation 6 by LM,CP: Ad hoc On-Demand Distance Vector Routing, Proc. 2nd IEEE Workshop on Mobile Computing Systems and Applications, 1999, pp. 90-100.
• Week 14.2: -- -- -- (Thanksgiving, Nov 27)
• Week 15.1 (Dec 2): Presentation 7 by LX,YH: Distributed Construction of Connected Dominating Set in Wireless Ad hoc Networks. 21st Annual Joint Conference of the IEEE Computer and Communications(INFOCOM), 2002.
• Week 15.2 (Dec 4): Presentation 8 by BW,WS: Web Prefetching: Costs, Benefits, and Performance, International Workshop on Web Content Caching and Distribution (WCW), August 2002.
  Term paper due at 5:00pm on December 4

Course Structure and Class Participation

Attendance is not compulsory. However, if you miss class, it is your responsibility to find out what was announced and what was covered.
The course format will be in two parts.

1. For the first part, the instructor will teach.
2. The second part involves active student participation and is planned as follows. Each team of 2-3 students will be required to present 1 topic. A paper will be assigned at least 3 weeks before its presentation date. Each student has to read and critique EACH paper, INCLUDING the ones his/her team is presenting, and submit a critique in class on the presentation day. If several papers are being discussed in a class, each of them should have a separate critique. Each critique should be anywhere between 1 to 2 printed pages (short and crisp) and should have the following format.
   • In your words, summary of the main contributions of the paper
   • Your evaluation of the contributions to advancing science and the state-of-the-art of the topic
   • State any deficiencies that you found in the paper
   • Provide directions for future improvements
   • List at least three of your most intelligent questions you would ask the author, or in this case, the presenters. The questions should not be "can you explain xyz on page 123?"

Class Participation Topics

1. Physical clock synchronization.
   Network Time Protocol (Version 3) Specification, Implementation and Analysis
   David L. Mills. RFC 1305, 1992.
   David Mill's home page for NTP. See IEEE TComm , ref [27] in particular.
   Improved algorithms for synchronizing computer network clocks, David Mills.
   Presenters: AW, JC
2. Replica placement and caching on the Internet
   Coordinated placement and replacement for large-scale distributed caches, Korupolu, M.R.; Dahlin, M., Page(s): 1317- 1329, IEEE TKDE, Nov/Dec. 2002.
   Mike's web page
   Amin's web page
   Presenters: US, PS
3. Algorithmic Challenges in Peer-to-Peer Systems. What are the topic-specific problems that pose new algorithm design challenges?
   Chord: a scalable peer-to-peer lookup protocol for internet applications. Ion Stoica, Robert Morris, David Liben-Nowell, David Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan, IEEE/ACM Transactions on Networking 11(1): 17-32 (2003)
   IPTPS Workshops
   Presenters: AB, MB
4. More Peer-to-peer. Topology Overlays - Algorithmic Challenges.
   Building topology-aware overlays using global soft-state, Zhichen Xu; Chunqiang Tang; Zheng Zhang, IEEE ICDCS, May 2003, Page(s): 500- 508.
   Presenters: SK, AS
5. More Peer-to-peer. Topology Overlays - Algorithmic Challenges.
   Decentralized p2p object replication system for weakly connected environments, Cetintemel, U.; Keleher, P.J.; Bhattacharjee, B.; Franklin, M.J., IEEE Transactions on Computers, 52(7), July 2003, pages 943-959.
   Presenters: WK, MS
6. Mobile ad-hoc networks: What are the algorithmic challenges? Routing ....
   AODV Routing algorithm
   Presenters: LM, CP
7. Mobile ad-hoc networks: What are the algorithmic challenges? Routing ....
   Virtual backbone for multicast in ad-hoc networks
   Presenters: LX, YH
8. Web Content Caching and Distribution: What are the algorithmic challenges?
   A course on Web Algorithms at ETH, Zurich
   International Workshops on Web Content Caching and Distribution (WCW),
   11th World Wide Web Conference (WWW), 2002, 12th World Wide Web Conference (WWW), 2003, Prashant's pubs
   Presenters: BW, WS

Auxiliary information

Literature sources: The following is a listing of journals and conferences that you may find useful in your literature search for your term paper.

1. Inter. Conference on Distributed Computing Systems (ICDCS)
2. IEEE Transactions on parallel and distributed systems (TPDS)
3. Journal of Parallel and Distributed Computing (JPDC)
4. ACM Symp. on Principles of Distributed Computing (PODC)
5. IEEE Symp. on Parallel and Distributed Processing (SPDP)
6. Distributed Computing
7. Journal of the ACM
8. Journal of Algorithms
9. Workshop on Distributed Algorithms (WDAG)
10. SIAM Journal on Computing