CS-345 Distributed Systems
Winter 2005

Course Schedule

Here is a list of the topics we will discuss, their scheduled dates and the related material we will cover. Each topic will be introduced with a lecture for which your are required to read the indicated (fraction of a) chapter from your textbook. After the introductory lecture, we will continue with presentations and discussions of related research papers.

The list includes a few papers everybody is responsible for (*) plus additional ones that are only the responsibility of the presenter (+). As a reference, I have also included a list of interesting related papers we will not have time to cover in class.

Schedule:

---

1. Introduction: Defining distributed systems and their goals, hardware and software concepts, system models. Design issues and words of wisdom (Jan. 4 & 6, 2005).
   Slides: Welcome to Distributed Systems, Introduction.
   • DSP2 Chap. 1.
   • (*) D. Clifford Neuman. Scale in Distributed Systems. In Casavant, T. and Singhal M. (eds.), Readings in Distributed Computing Systems, Los Alamitos, CA, 1994, pp 463-489.
     Presenter (Date): Instructor (Jan. 6)
     
   • (+) B. Lampson. Hints for Computer System Design. In Proc. of the ACM Symposium on Operating Systems Principles, Dec. 1983.
   • (+) J. Saltzer, D. Reed and D. Clark. End-to-End Arguments in System Design. ACM Transactions on Computer Systems, 2(4):277-288, November 1984.

---

2. Communication: Basics of communication, remote procedure calls and remote object invocation(Jan. 11 & 13, 2005)
   Slides: Communication.
   • DSP2 Chap. 2 (2.0-2.3)
   • (*) A. D. Birrell and B. J. Nelson. Implementing Remote Procedure Calls, ACM Transaction on Computer Systems, 2(1), Feb. 1984, pp 271-290.
     Presenter (Date): Jack Lange (Jan. 11)
     Slides
     Selected summary
   • (+) M. D. Schroeder and M. Burrows. Performance of the Firefly RPC. In Proc. of the 12th Symposium on Operating System Principles, 1989.
   • (+) J. Maassen, R. van Nieuwpoort, R. Veldema, H. E. Bal and A. Plaat. An efficient implementation of Java's remote method invocation. In Proc. of the 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1999.
   • (*) A. Joseph, A. deLespinasse, J. Tauber, D. Gifford and M. Kaashoek. Rover: A Toolkit for Mobile Information Access. In Proc. of the 15th Symposium on Operating System Principles, 1995.
     Presenter (Date): Yi Qiao (Jan. 13)
     Slides
     Selected summary
   • (+) G. Hamilton, M. Powel and J. Mitchell. Subcontract: a flexible base for distributed programming. In Proc. of the 14th Symposium on Operating Systems Principles, 1994.
   • (+) A. Birrell, G. Nelson, S. Owicki and E. Wobber. Network Objects. In Proc. of the 14th Symposium on Operating System Principles, 1993.
   
   

   ---

   
   Related papers we won't cover:
   • B. Bershad, T. Anderson, E. Lazowsa and H. Levy. Lightweight remote procedure call. In Proc. of the 12th Symposium on Operating System Principles, 1989.
   • N. Carriero and D. Gelernter. Linda in context. Communications of the ACM 32(4), April 1989, pp 444-458.
   • G. Eisenhauer, F. E. Bustamante and K. Schwan. Native Data Representation: An Efficient Wire Format for High-Performance Computing, IEEE Transaction on Parallel and Distributed Systems, 13 (12), pp 1234-1246, 2002.
     
   • G. Banaver, T. Chandra, R. Strom, D. Sturman. A Case for Message Oriented Middleware, in Proc. 13th International Symposium on Distributed Computing (DISC) (invited lecture), Sep. 1999, pp 1-18.
     
   • T. von Eicken, D. E. Culler, S. C. Goldstein and K. E. Schauser. Active messages: a mechanism for integrated communication and computation. In Proc. of the 19th Annual International Symposium on Computer Architecture, 1992.
   • D.A. Wallach, W.C. Hsieh, K.L. Johnson, M.Frans Kaashoek and W.E. Weihl. Optimistic Active Messages: A Mechanism for Scheduling Communication with Computation. In Proc. PPoPP'95, July 1995.

---

3. Wide-area distributed experimentation and PlanetLab: Issues evaluating wide-area distributed systems and brief introduction to PlanetLab (TBD) .
   • (*) L. Peterson, T. Anders, D. Culler and T. Roscoe. A Blueprint for Introducing Disruptive Technology into the Internet. In Proc. of the first ACM Workshop on Hot-Topics in Networks (HotNets-I), Oct. 2002.
     Presenter (Date): Stefan Birrer (TBD)
     
   • (+) A.Bavier, L.Peterson. M. Wawrzoniak, S. Karlin, T. Spalink, T. Roscoe, D. Culler, B. Chun and M. Bowman. Operating System Support for Planetary-Scale Network Services.
   • (+) B. Chun and T. Spalink. Slice Creation and Management. Tech. Report PDN-03-013, PlanetLab, July 2003.
   
   

   ---

   
   Related papers we won't cover:
   • A.Nakao, L. Peterson and A. Bavier. A Routing Underlay for Overlay Networks. In Proc. of the ACM SIGCOMM Conf, August 2003.

---

4. Processes: Clients, servers, code migration and software agents (Jan. 18 & 20, 2005)
   Slides: Processes.
   • DSP2 Chap. 3 (TBD)
   • (*) M. Welsh, D. Culler and E. Brewer. SEDA: An Architecture for Well-Conditioned, Scalable Internet Services. In Proc. of the 18th Symposium on Operating Systems Principles, 2001.
     Presenter (Date): Aaron Beach (Jan. 18)
     Slides
     Selected summary
   • (+) G. Banga, P. Druschel and J. Mogul. Resource containers: A new facility for resource management in server sysytems. In Proc. of the 3rd Symposium on Operating Systems Design and Implementation, 1999.
   • (*) F. Douglis and J. K. Ousterhout, Transparent Process Migration: Design Alternatives and the Sprite Implementation, Software Practice and Experience, vol. 21, no. 8 (August 1991), pp 757-785.
     Presenter (Date): Stefan Birrer (Jan. 20)
     
   • (+) E. Jul, H. Levy, N. Hutchinson and A. Black. Fine-grained Mobility in the Emerald System. ACM TOCS 6(1), Feb. 1988.
   
   

   ---

   
   Related papers we won't cover:
   • C. Hauser, C. Jacobi, M. Theimer, B. Welch, M. Weiser Using Threads in Interactive Systems: A Case Studby, in Proc. of the 14th Symposium on Operating Systems Principles, Dec. 1993, pp 94-105.
   • J. K. Ousterhout Why Threads are a Bad Idea (for most purposes), 1996.
   • J. K. Ousterhout, A. R. Cherenson, F. Douglis, M. Nelson, and B. Welch, The Sprite Network Operating System, IEEE Computer 21(2), Feb. 1988, pp 22-36.
   • R. Gray, D. Kotz, G. Cybenko, D. Rus. Mobile Agents: Motivations and State-of-the-Art Systems. Dartmouth Technical Report TR2000-365, April 2000. To appear as a chapter in Jeffrey M. Bradshaw, editor, Handbook of Agent Technology, AAAI/MIT Press, 2000. In Press.
   • H.S. Nwana and D.T. Ndumu. A Perspective on Software Agents Research. The Knowledge Engineering Review, Vol 14, No 2, 1999.

---

5. Naming: Naming and locating entities, removing unreferenced entities (Jan. 25 & 27, 2005).
   • DSP2 Chap. 4
   • (*) Jaeyeon Jung, Emil Sit, Hari Balakrishnan, and Robert Morris, DNS Performance and the Effectiveness of Caching.ACM SIGCOMM Internet Measurement Workshop, Nov. 2001.
     Presenter (Date): Zhichun Li (Jan. 25)
     
   • (+) P. Mockapetris and K. Dunlap.Development of the Domain Name System. In Proc. o the ACM SIGCOMM Conf., 1988.
   • (+) P. Danzig, K. Obracza and A. Kumar.An Analysis of Wide-Area Name Server Traffic. In Proc. o the ACM SIGCOMM Conf., 1992.
   • (*) William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, Jeremy Lilley, The Design and Implementation of an Intentional Naming System, Proc. of the 17th ACM Symposium on Operating Systems Principles, Dec. 1999.
     Presenter (Date): Yao Zhao (Jan. 27)
     
   • (+) M. Balazinska, H. Balakrisnan and D. Karger. INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery. In Proc. of International Conference on Pervasive Computing, 2002.
   • (+) Y. Hu, D. Rodney and P. Druschel. Design and Scalability of NLS, a Scalable Naming and Location Service. In Proc. of IEEE INFOCOM, 2002.
   
   

   ---

   
   Related papers we won't cover:
   • F. Bustamante, P. Widener and K. Schwan. Scalable Directory Services Using Proactivity. In Proc. of Supercomputing, 2002.
   • David R. Cheriton and Timothy P. Mann, Decentralizing a Global Naming Service for Improved Performance and Fault Tulerance, ACM Transactions on Computer Systems 7(2):147:183, 1989.
   • E. Pitoura and G. Samaras Locating Objects in Mobile Computing, in IEEE Transaction on Knowledge and Data Engineering 13(4), Jul/Aug 2001, pp 571-592.
     
   • M. van Steen, F. Hauc, G. Ballintijn and A. Tanenbaum. Algorithmic Design of the Globe Wide-Area Location Service. The Computer Journal, 41(5), 1998.

---

6. Synchronization: Synchronization in distributed systems, logical time, global state, elections and mutual exclusion (Feb 1 & 3, 2005).
   • DSP2 Chap. 5 (5.0-5.5)
   • (*) L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM, Vol. 21, No. 7 (July 1978), pp. 558-565.
     Presenter (Date): Taylor Raack (Feb. 1)
     
   • (+) M. Raynal and M. Singhal, Logical Time: Capturing Causality in Distributed Systems, in IEEE Computer, 29(2), Feb. 1996, pp 49-56.
   • (+) R. Schwarz and F. Mattern, Detecting Casual Relationships in Distributed Computation: In Search of the Holy Grail, Distributed Computing, 1994.
   • (*) M. Chandy and L. Lamport, Distributed Snampshots: Determining Global States of Distributed Systems, ACM Transactions on Computer Systems, 3(1), Feb. 1985, pp 63-75.
     Presenter (Date): Manan Sanghi (Feb. 3)
     
   • (+) J. Helary, C. Jard, N. Plouzeau and M. Raynal.Detection of Stable properties in Distributed Applications. In Proc. o the 11th International Conference on Distributed Computer Systems, 1986.
   • (+) R. Cooper and K. Marzullo. Consistent detection of global predicates. In Proc. of the ACM/ONR Workshop on Parallel and Distributed Debugging, 1991.
   
   

   ---

   
   Related papers we won't cover:
   • D. Mills, Improved Algorithms for Synchronizing Computer Network Clocks, IEEE/ACM Transactions on Networks, 3(3), Jun. 1995, pp 245-254.
   • F. Cristian. A Probabilistic Approach to Distributed Clock Synchronization. In Proc. of the 9th International Conference on Distributed Computing Systems, 1989.
   • K. Marzullo and G. Neiger. Detection of global predicates: Techniques and their limitations.In Proc. of the 5th International Workshop on Distributed Algorithms (WDAG), 1991.
   • C. Chase and V. Garg. Detection of global state predicates. Distributed Computing, 11:191-201, 1998.

---

7. Consistency and replication: Data replication, scalability, and consistency (Feb. 8 & 10, 2005).
   • DSP2 Chap. 6
   • (*) D. Terry, K. Petersen, M. Spreitzer and M. Theimer, The Case for Non-Transparent Replication: Examples from Bayou, IEEE Data Engineering, 21(4), Dec. 1998, pp 12-20
     Presenter (Date): Yi Qiao(Feb. 8)
     
   • (+) Karin Petersen, Mike J. Spreitzer, Douglas B. Terry, Marvin M. Theimer and Alan J. Demers, Flexible Update Propagation for Weakly Consistent Replication. In Proc. of the 16th ACM Symposium on Operating Systems Principles, 1997.
   • (*) H. Yu and A. Vahdat, Design and Evaluation of a Continuous Consistency Model, in Proc. 4th Symposium on Operating System Design and Implementation, USENIX, 2000
     Presenter (Date): Taylor Raack (Feb. 10)
     
   • (+) S. Shah, A. Bernard, V. Sharma, K. Ramamritham, P. Shenoy. Maintaining temporal coherency of cooperating dynamic data repositories. In Proc. of the 28th International Conference on Very Large Data Bases, 2002.
   • (+) V. Gopatakrishnan, B. Sitaghi, B. Bhattacharjee and P. Keleher. Adaptive Replication in Peer-to-Peer Systems. ICDCS, 2004.
   
   

   ---

   
   Related papers we won't cover:
   • Y. Saito and M. Shapiro, Optimistic Replication, Tech. Report MSR-TR-2003-60, Oct. 2003
   • P. Keleher, A. Cox, and W. Zwaenepoel, Lazy Release Consistency for Software Distributed Shared Memory, in Proc. 20th Symposium on Computer Architecture, 1993
   • O. Wolfson, S. Jajodia, Y. Huang. An adaptive data replication algorithm. ACM Transaction on Database Systems, 22(2):255-314, 1997.
   • J. Gray, P. Helland, P. O'Neil, and D. Shasha. The dangers of replication and a solution. In Proc. of the ACM SIGMOD International Conference on Management of Data, 1996.

---

8. Fault tolerance: Making distributed systems fault tolerant, reliable and resilient multicasting (Feb. 15 & 17, 2005).
   • DSP2 Chap. 7
   • (*) J. Yin, J-P. Martin, A. Venkataramani, L. Alvisi, M. Dahlin, Separating Agreement from Execution for Byzantine Fault Tolerant Systems, in Proc. of 19th Symposium on Operating Systems Principles, Bolton Landing, Oct. 2003, pp 253-267
     Presenter (Date): Manan Sanghi (Feb. 15)
     
   • (+) M. Castro, R. Rodrigues and B. Liskov, BASE: Using abstraction to improve fault tolerance, ACM Trans. Comput. Syst. 21(3), 2003, pp 236-269.
   • (+) F. B. Schneider. Implementing Fault-tolerant Services using the State Machine Approach: a Tutorial. ACM Computing Surveys (CSUR), 22(4):299-319, December 1990.
   • (*) S. Birrer, D. Lu, F. Bustamante, Y. Qiao and P. Dinda. FatNemo: Building a Resilient Multi-Source Multicast Fat-Tree. In Proc. of the Ninth International Workshop on Web Content Caching and Distribution, 2004.
     Presenter (Date): Fabian Bustamante (Feb. 17)
     
   • (+) S. Banerjee, S. Lee, B. Bhattacharjee and A. Srinivasan. Resilient Multicast Using Overlays. In Proc. of ACM SIGMETRICS, 2003.
   • (+) M. Castro, P. Druschel, A-M. Kermarrec, A. Nandi, A. Rowstron and A. Singh. SplitStream: High-Bandwidth Multicast in Cooperative Environments. In Proc. of Symposium on Operating Systems Principles, 2003.
   
   

   ---

   Related papers we won't cover:
   • S. Birrer and F. Bustamante. Nemo- Resilient Peer-to-Peer Multicast without the Cost. In Proc. of the 12th Annual Multimedia Computing and Networking Conference, 2005.
   • V. Padmanabhan, H. Wang and P. Chou. Resilient peer-to-peer streaming. In. Proc. of IEEE ICNP, 2003.
   • R. Haskin, Y. Malachi, W. Sawdon, and G. Chan, Recovery Management in Quicksilver, ACM Transactions on Computer Systems, 6(1), Feb. 1998, pp 82-108

---

9. Security:Secure communication and authorization in distributed systems (Feb. 22 & 24, 2005).
   • DSP2 Chap. 8
   • (*) D. Malkhi, N. Nisan, B. Pinkas, Y. Sella. Fairplay - A Secure Two-Party Computation System. In USENIX Security, 2004.
     Presenter (Date): Zhichun Li (Feb. 22)
     
   • (+) S. Ajmani, R. Morris, and B. Liskov. A trusted third party computation service. Technical Report MIT-LCSTR- 847, MIT, May 2001.
   • (+) S. Zdancewic, L. Zheng, N. Nystrom, and A. C. Myers. Untrusted hosts and confidentiality: Secure program partitioning. ACM Transactions on Computer Systems, 20(3):283 328, 2002.
   • (*) S. Staniford, V. Paxson and N. Weaver. How to Own the Internet in Your Spare Time. In Proc. of the USENIX Security Symposium, 2002
     Presenter (Date): Yao Zhao (Feb. 24)
     
   • (+) D. Moore, C. Shannon, G. M. Voelker and S. Savage. Internet Quarantine: Requirements for Containing Self-Propagating Code. In Proc. of Infocom, 2003.
   • (+) S. Chen and Y. Tang. Slowingdown Internet Worms. In Proc. of 24th International Conference on Distributed Computing Systems, 2004.
   
   

   ---

   
   Related papers we won't cover:
   • J. Steiner, C. Neuman, and J. Schiller, Kerberos: Aun Authenitcation Service for Open Network Systems. In Proc. Winter Tech. Conf. Usenix, 1988.
   • S.M. Bellovin and M. Merritt. Limitations of the Kerberos Authentication System. In Proc. USENIX Conference, Winter 1991.
   • J. Howell and D. Kotz, End-to-End Authorization, in Proc. of the 4th Symposium on Operating System Design and Implementation, 2000.
   • R. Sekar, V. N. Venkatakrishnan, S. Basu, S. Bhatkar, D.C. DuVarney, Model-Carrying Code: A Practical Approach for Safe Execution. In Proc. 19th Symposium on Operating Systems Principles, 2003.
   • M. Blaze, J. Feigenabum, J. Ioannidis, and A. D. Keromytis, The Role of Trust Management in Distributed Systems Security, in Secure Internet Programming: Security Issues for Mobile and Distributed Objects, Lect. Notes Comp. Sc., Springer-Verlag, 1999, pp 185-210
     

---

10. Review of major distributed systems paradigms: Distributed object systems, Distributed file systems, Distributed document-based systems, and Distributed coordination-based systems (Mar. 1 & 3, 2005).
    • DSP2 Parts of Chaps. 9-12
    • (*) M. Freedman, E. Freudenthal and D. Mazieres. New York University. Democratizing Content Publication with Coral. In Proc. NSDI, 2004.
      Presenter (Date): Aaron Beach (Mar. 1)
      
    • (+) G. Pierre and M. van Steen. Design and Implementation of a User-Centered Content Delivery Network. In Proc. of the Third IEEE Workshop on Internet Applications, 2003.
    • (*) Y. Saito, C. Karamanolis, M. Karlsson and M. Mahalingam. Taming aggressive replication in the Pangaea wide-area file system, In Proc. OSDI, 2002.
      Presenter (Date): Jack Lange (Mar. 3)
      
    • (+) B. Groenvall, A. Westerlund and S. Pink, The Design of a Multicast-based Distributed File System, in Proc. of the 3rd Symposium on Operating System Design and Implementation, 1999.
    • (+) R. Bhagwan, K. Tati, Y. Cheng, S. Savage and G. Voelker. Total Recall: System Support for Automated Availability Management.In Proc. of NSDI, 204.
    
    

    ---

    
    Related papers we won't cover:
    • T. Anderson , M. Dahlin , J. Neefe , D. Patterson , D. Roselli , R. Wang. Serverless network file systems. In Proc. of the 15th ACM symposium on Operating systems principles, 1995.
    • W. Bolosky, J. Douceur, D. Ely and M. Theimer.Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs.ACM SIGMETRICS Performance Evaluation Review, 28(1), June 2000.
    • G. Pierre and M. van Steen. Design and Implementation of a User-Centered Content Delivery Network. In Proc. of the Third IEEE Workshop on Internet Applications, 2003.
    • M. van Steen, P. Homburg and A. S. Tanenbaum, Globe: A Wide-Area Distributed System, IEEE Concurrency 7(1), Jan-Mar 1999, pp 70-78.
    • Y. Qiao, D. Lu, F. Bustamante, P. Dinda and S. Birrer. Looking at the Server-Side of Peer-to-Peer Systems. In Proc. of the 7th Workshop on Languages, Compilers and Run-time Support for Scalable Systems, October 2004
    • Y. Qiao and F. E. Bustamante The Effect of Lasting Friendships in P2P Protocols,submitted for publication. Also published as Tech. Report NWU-CS-23, Department of Computer Science, Northwestern University, 2003.
    • A. Carzaniga, D.S. Rosenblum, and A.L. Wolf, Design and Evaluation of a Wide-Area Event Notification Service, ACM Transactions on Computer Systems, 19(3), August 2001, pp. 332-383.

---

11. Project presentations (Mar. 8 & 10, 2005).

---

12. Take-home exam (Mar. 14 to 18, 2005)

---