CS-495 Distributed Systems
Winter 2004

Course Outline

• Introduction (1/6-1/8): Defining distributed systems and their goals, hardware and software concepts, the client-server model and architecture, modern architectures for distributed systems.
  • DSP2 Chap. 1. (Thursday 1/8)
  • 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 (Tue. 1/8)
    Selected summary
  • B. Lampson, Hints for Computer System Design, ACM Symposium on Operating Systems Principles, Dec. 1983, pp 33-48.
    Presenter (Date): Instructor (Tue. 1/8)
    Selected summary

• Communication (1/13-1/15): Basics of communication, remote procedure calls, remote object invocation, message-oriented and stream-oriented communication.
  • DSP2 Chap. 2 (Tuesday: from 2.0 to 2.3 included / Thursday: from 2.4 on)
  • 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.
    Presenter (Date): Stefan Birrer (Tue. 1/13)
    Slides
    Selected summary
  • 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): James Newell (Tue. 1/13)
    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.
    Presenter (Date): Stefan Birrer (Thu. 1/15)
    Slides
    Selected summary
  • 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.
    Presenter (Date): Ashish Gupta (Thu. 1/15)
    Slides
    Selected summary

• Wide-area distributed systems and PlanetLab (Thursday 15th - right after class!): Issues with wide-area distributed systems and brief introduction to PlanetLab.
• Processes (1/20-1/22): Clients, servers, code migration and software agents.
  • DSP2 Chap. 3 (Tuesday: up to and including 3.3 / Thursday: from 3.4 on)
  • C. Hauser, C. Jacobi, M. Theimer, B. Welch, M. Weiser Using Threads in Interactive Systems: A Case Study, in Proc. of the 14th Symposium on Operating Systems Principles, Dec. 1993, pp 94-105.
    Presenter (Date): Steve Gordon (Tue. 1/20)
    Slides
    Selected summary
  • 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): Yi Qiao (Tue. 1/20)
    Slides
    Selected summary
  • E. Jul, N. Hutchinson, A. Black, Fine-Grained Mobility in the Emerald System, ACM Transactions on Computer Systems 6(1), Feb. 1988, pp 109-133.
    Presenter (Date): Bob Adolf (Thu. 1/22)
    Slides
    Selected summary
  • R. S. Gray, Agent Tcl: A Flexible and Secure Mobile-Agent System, in Proc. of the 4th Annual Tcl/Tk Workshop, USENIX, 1996.
    Presenter (Date): Geet Duggal (Thu. 1/22)
    Slides
    Selected summary
  • Additional readings
    • 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.
    • J. K. Ousterhout Why Threads are a Bad Idea (for most purposes), 1996.

• Naming (1/27-1/29): Naming and locating entities, removing unreferenced entities.
  Moderator: Stefan Birrer
  • DSP2 Chap. 4
  • 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.
    Presenter (Date): Bob Adolf (Tue. 1/27)
    Slides
    Selected summary
  • 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): Ken Chandonait (Thu. 1/29)
    Slides
    Selected summary
  • 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.
    Presenter (Date): Geet Duggal (Thu. 1/29)
    Slides
    Selected summary
  • 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): Bin Lin (Thu. 1/29)
    Slides
    Selected summary

• Synchronization (1/29-2/3): Synchronization in distributed systems, logical time, global state, elections and mutual exclusion.
  Moderator: Bob Adolf
  • DSP2 Chap. 5
  • D. Mills, Improved Algorithms for Synchronizing Computer Network Clocks, IEEE/ACM Transactions on Networks, 3(3), Jun. 1995, pp 245-254.
    Presenter (Date): Steve Gordon (Tue. 2/10)
    Slides
    Selected summary
  • M. Raynal and M. Singhal, Logical Time: Capturing Causality in Distributed Systems, in IEEE Computer, 29(2), Feb. 1996, pp 49-56.
    Presenter (Date): Yi Qiao (Tue. 2/10)
    Slides
    Selected summary
  • 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): Geet Duggal (Tue. 2/10)
    Slides
    Selected summary
  • R. Schwarz and F. Mattern, Detecting Casual Relationshops in Distributed Computation: In Search of the Holy Grail, Distributed Computing, 1994.
    Presenter (Date): Joseph Jorgensen (Tue. 2/10 - w/o presentation)
    Slides
    Selected summary

• Consistency and replication (2/5-2/10): Data replication, scalability, and consistency
  Moderator: Yi Qiao
  • DSP2 Chap. 6
  • Y. Saito and M. Shapiro, Optimistic Replication, Tech. Report MSR-TR-2003-60, Oct. 2003
    Presenter (Date): Bob Adolf
    Slides
    Selected summary
  • P. Keleher, A. Cox, and W. Zwaenepoel, Lazy Release Consistency for Software Distributed Shared Memory, in Proc. 20th Symposium on Computer Architecture, 1993
    Presenter (Date): Ken Chandonait
    Slides
    Selected summary
  • 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): Bin Lin
    Slides
    Selected summary
  • 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): Steve Gordon
    Slides
    Selected summary

• Fault tolerance (2/12-2/17): Making distributed systems fault tolerant, reliable and resilient multicasting.
  Moderator: Ananth Sundararaj
  • DSP2 Chap. 7
  • 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
    Presenter (Date): Joseph Jorgensen
    Slides
    Selected summary
  • M. Castro, R. Rodrigues and B. Liskov, BASE: Using abstraction to improve fault tolerance, ACM Trans. Comput. Syst. 21(3), 2003, pp 236-269
    Presenter (Date): Ananth Sundararaj
    Slides
    Selected summary
  • S. Birrer and F. E. Bustamante, Resilient Overlay Multicast from the Ground Up, submitted for publication. Also published as Tech. Report NWU-CS-03-22, Department of Computer Science, Northwestern University, 2003
    Presenter (Date): James R. Newell
    Slides
    Selected summary
  • 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): Ananth Sundararaj
    Slides
    Selected summary

• Security (2/19-2/24):Secure communication and authorization in distributed systems.
  Moderator:
  • DSP2 Chap. 8
  • J. Steiner, C. Neuman, and J. Schiller, Kerberos: Aun Authenitcation Service for Open Network Systems, in Proc. Winter Tech. Conf. Usenix, 1988, pp 191-202
    Presenter (Date): Ken Chandonait
    Slides
    Selected summary
  • 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
    Presenter (Date): Yi Qiao
    Slides
    Selected summary
  • J. Howell and D. Kotz, End-to-End Authorization, in Proc. of the 4th Symposium on Operating System Design and Implementation, USENIX, 2000
    Presenter (Date): James R. Newell
    Slides
    Selected summary

• Review of major distributed systems paradigms (2/26-3/4): Distributed object systems, Distributed file systems, Distributed document-based systems, and Distributed coordination-based systems.
  Moderator:
  • DSP2 Parts of Chaps. 9-12
  • 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, USENIX, 1999, pp 251-264
    Presenter (Date): Stefan Birrer
    Slides
    Selected summary
  • 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
    Presenter (Date):Joseph Jorgensen
    Slides
    Selected summary
  • 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
    Presenter (Date):Bob Adolf
    Slides
    Selected summary

• Project presentations (3/9-3/11):
• Take-home exam (3/16)

Fabián E. Bustamante

Last modified: Thu Jan 8 11:43:19 CDT 2003