Reading Assignment

Presentation Format

Please read carefully

Each week this class will cover a group of papers that focuses on a specific aspect of software engineering issues in building distributed systems. Students are expected to read all the papers in the group that will be presented (the number of presentations depends on the number of students in class). At the beginning of the term, each paper will be assigned to a student who will be presenting the paper. Presentations will be limited to 15 minutes. While students are welcome to present papers as they wish, here is an outline of a presentation that should help you get started.

  1. Start by stating the thesis or the goals of the paper, i.e., what is the paper trying to achieve.
  2. Next, state the major contributions of the work, i.e., what is new about the work.
  3. Briefly describe each contribution. Choose one (or two) contribution(s) that you think is most interesting or novel and explain it in some detail.
  4. If there are experiments in the paper that highlight the benefits of the work, present some of these results. Ideally, the results you show will focus on the contributions that you explained in detail.
  5. Next, present related work in the area, i.e., how is this work related to other projects or systems.
  6. Present your conclusions about the work, i.e., does the paper achieve what it set out to achieve.
If students use slides, please use at least 20-24 point font for text. For a 15 minute presentation, do not use more than 15 slides or else the presentation will appear rushed. Students are welcome to send slides to the instructor a week before the presentation to get additional help.

After the presentation the student is expected to lead a 20-30 minute in-depth discussion of the paper (the length of the discussion will depend on the number of students in the class). This discussion should aim to answer the following questions:

  1. What were the main contributions of the work?
  2. What were the advantages and disadvantages of the approach?
  3. What are potential avenues for further work and improvements?
To aid in this discussion, each student presentation must end with a list of 5 specific questions that the student can ask other students and should be prepared to answer (the student should preferably have the answers at the end of the slides).

The answers to these questions should not be obvious, i.e. they should not be stated clearly in the paper. Instead, the questions should help in critial analysis of the paper. For example, suppose one of the stated contributions of the paper is that it "makes programming event-based software much less error-prone". One question might be: why was the old method error-prone and how the paper circumvent the programming task from making mistakes?

Paper list

1. Basic concepts:

  1. Time, clocks, and the ordering of events in a distributed system. Leslie Lamport (1978). Communications of the ACM 21 (7): (*) (Liu Peng on Feb 24)
  2. Middleware: A model for distributed systems services P. Bernstein. Communications of the ACM, Feb. 1996 (*) (Zhu Lin on Feb 24)
  3. An Introduction to Software Architecture. David Garlan and Mary Shaw, CMU-CS-94-166 (*) (Li Yueqi on Feb 26)
  4. On the Duality of Operating System Structures, Lauer and Needham, Operating Systems Review, 13,2 April 1979, pp. 3-19 (*) (Huang Shaoming on Feb 26)
  5. Concepts and experiments in computational reflection. Maes, P. 1987. SIGPLAN Not. 22, 12 (Dec. 1987), 147-155 (*) (Tang Yilun on March 3rd)
  6. An overview of AspectJ. G. Kiczales; ACM Comput. Surv. 28, 4es (Dec. 1996), Article 154. (*) (WONG Kin Man on March 3rd)
  7. On the criteria to be used in decomposing systems into modules. Parnas, D. L. Commun. ACM 15, 12 (Dec. 1972) (*) (Zhang Wei on March 5th)
Background readings:
  1. The Apache HTTP Server Project, IEEE Internet Computing archive Volume 1 , Issue 4 (July 1997) Pages: 88 - 90
  2. One Document to Bind Them: Combining XML, Web Services, and the Semantic Web, Harry Halpin, WWW2006
  3. Managing Complexity: Middleware Explained Andrew T. Campbell, Geoff Coulson, and Michael E. Kounavis IT Professional, Vol. 1, No. 5, September/October 1999.

2. Programming models for distributed systems:

  1. Implementing remote procedure call. A. D. Birrell and B. J. Nelson. ACM Transactions on Computer Systems, 2, Jan. 1984 (Tang YiLun on March 5th)
  2. MapReduce: Simplified Data Processing on Large Clusters. Jeffrey Dean and Sanjay Ghemawat OSDI'04: Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, December, 2004. (Liu Peng on March 10th)
  3. "Principled Design of the Modern Web Architecture Fielding, Roy T.; Taylor, Richard N. , ACM Transactions on Internet Technology (TOIT) (Li Yueqi on March 10th)
  4. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly European Conference on Computer Systems (EuroSys), Lisbon, Portugal, March 21-23, 2007 (Zhang Wei on March 12th)
  5. Streamflex: high-throughput stream programming in java. Spring, J. H., Privat, J., Guerraoui, R., and Vitek, J. 2007. SIGPLAN Not. 42, 10 (Oct. 2007), 211-228 (Liu Peng on March 12th)
Background Readings:
  1. Distributed object-based programming systems. R. S. Chin and S. T. Chanson. ACM Computing Surveys, 23(1), Mar. 1991 (*)
  2. The many faces of publish/subscribe Eugster, P. T., Felber, P. A., Guerraoui, R., and Kermarrec, A. 2003. ACM Comput. Surv. 35, 2 (Jun. 2003), 114-131
  3. A Case for Message Oriented Middleware. Banavar, G., Chandra, T. D., Strom, R. E., and Sturman, D. C. 1999. In Proceedings of the 13th international Symposium on Distributed Computing
  4. CORBA: Integrating Diverse Applications Within Distributed Heterogeneous Environments. By Steve Vinoski. IEEE Communications, February 1997.
  5. A Discussion of the Object Management Architecture. Technical Specification. The Object Management Group. Read: Chapter 1 (6 pages) , Chapter 2 (6 pages) , Chapter 3 (7 pages) Chapter 4 (12 pages) . Note, the entire specification on the OMG site is pretty long. Do NOT print the entire file, required reading is [Ch1, Ch2, Ch3, and Ch4] .
  6. To RPC or not to RPC?
  7. Too Much Middleware.Michael Stonebraker. SIGMOD Records V2.3.

4. Naming and Lookup services

  1. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan, ACM SIGCOMM 2001, San Deigo, CA, August 2001, pp. 149-160 (Tang Yilun on March 17th)
  2. Enterprise application integration by means of a generic CORBA LDAP gateway. Jandl, M., Radinger, W., Szep, A., and Goeschka, K. M. 2002. In Proceedings of the 24th international Conference on Software Engineering (Orlando, Florida, May 19 - 25, 2002). ICSE '02. ACM, New York, NY, 711-711

5. Server-side architecture:

Locking
  1. Lock allocation. Emmi.M, Fischer, J. S., Jhala, R., and Majumdar, R. In Proceedings of the 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Nice, France, January 17 - 19, 2007). POPL '07. ACM, New York, NY, 291-296
  2. Scalable lock-free dynamic memory allocation. Michael, M. M. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation (Washington DC, USA, June 09 - 11, 2004). PLDI '04. ACM, New York, NY, 35-46 (Huang Shaoming on March 17th)
Software Transactional Memory
  1. Software Transactional Memory: Why is it Only a Research Toy? Cascaval, C., Blundell, C., Michael, M., Cain, H. W., Wu, P., Chiras, S., and Chatterjee, S. 2008. . Queue 6, 5 (Sep. 2008), 46-58. (*)
  2. A flexible framework for implementing software transactional memory. Herlihy, M., Luchangco, V., and Moir, M. 2006. In Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (Wong Kin Man on March 19th)
Effecient server-side architecture
  1. SEDA: an architecture for well-conditioned, scalable internet services. Welsh, M., Culler, D., and Brewer, E. 2001. In Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles (Banff, Alberta, Canada, October 21 - 24, 2001). SOSP '01. ACM, New York, NY, 230-243. (Li Yueqi on March 19th)
  2. Capriccio: scalable threads for Internet services. R. von Behren, J. Condit, F. Zhou, G. C. Necula, and E. Brewer. In Proc. 19th SOSP, October 2003. (Huang Shaoming on March 24th)
Event-based programming:
  1. Cooperative Task Management Without Manual Stack Management. Adya, A., Howell, J., Theimer, M., Bolosky, W. J., and Douceur, J. R. In Proceedings of the General Track of the Annual Conference on USENIX Annual Technical Conference (June 10 - 15, 2002) (Zhang Wei on March 24th)
  2. Events can make sense. Krohn, M., Kohler, E., and Kaashoek, M. F. In 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference (Santa Clara, CA, June 17 - 22, 2007)
  3. Combining events and threads for scalable network services. P. Li and S. Zdancewic. In Proc. 2007 PLDI, Jun 2007. (Huang Shaoming on April 28th)
Server-side architecture issues:
  1. The Object-Oriented Design and Performance of JAWS: A High-performance Web Server Optimized for High-speed Networks,James Hu, Irfan Pyarali, and Douglas C. Schmidt, (updated July 18) The Parallel and Distributed Computing Practices journal, special issue on Distributed Object-Oriented Systems, edited by Maria Cobband Kevin Shaw, Vol. 3, No. 1, March 2000. (*)
  2. Exploiting ADLs to specify architectural styles induced by middleware infrastructures. E. Di Nitto and D. Rosenblum. In Proceedings of the 1999 International Conference on Software Engineering
  3. Experience with performing architecture tradeoff analysis. R. Kazman, M. Barbacci, M. Klein, S. J. Carrière, and S. G. Woods. In Proceedings of the 1999 International Conference on Software Engineering, (Tang Yilun on April 30th)
Micro-kernel and reflection:
  1. Improving IPC by kernel design. J. Liedtke. In Proceedings of the 14th ACM Symposium on OS Principles, 1993. (Liu Peng on April 7th)
  2. On micro-kernel construction. J. Liedtke. In Proceedings of the 15th ACM Symposium on OS Principles, 1995.
  3. Monitoring, security, and dynamic configuration with the dynamicTAO reflective ORB. Kon, F. et al. In ACM Middleware 2000 (Wong Kin Man on April 7th)
SOA and AJAX:
  1. Efficient exploration of service-oriented architectures using aspects Kruger, I. H., Mathew, R., and Meisinger, M. 2006. . In Proceedings of the 28th international Conference on Software Engineering
  2. Doloto: code splitting for network-bound web 2.0 applications. Livshits, B. and Kiciman, E. 2008. In Proceedings of the 16th ACM SIGSOFT international Symposium on Foundations of Software Engineering (Atlanta, Georgia, November 09 - 14, 2008). SIGSOFT '08/FSE-16. ACM, New York, NY, 350-360. (Li Yueqi on April 16th)
  3. AspectJ2EE = AOP + J2EE: Towards an aspect based, programmable and extensible middleware framework (2004) by Tal Cohen, Joseph (yossi) Gil In Proc. ECOOP 2004, volume 3086 of LNCS (Wong Kin Man on April 16th)
Background readings:
  1. The Tenenbaum-Tovalds debate: Monolithic vs. Micro-kernel.
Debugging/Fault location:
  1. D3S: debugging deployed distributed systems. Liu, X., Guo, Z., Wang, X., Chen, F., Lian, X., Tang, J., Wu, M., Kaashoek, M. F., and Zhang, Z. 2008. In Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation (Zhang Wei on April 23rd)
  2. Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code. SOSP 2001 (Zhu Lin on April 23rd)
  3. Finding and Reproducing Heisenbugs in Concurrent Programs. OSDI 2008. (Zhu Lin on April 28th)
  4. RacerX: Effective, Static Detection of Race Conditions and Deadlocks, SOSP 2003.
  5. MUVI: Automatically Inferring Multi-Variable Access Correlations and Detecting Related Semantic and Concurrency Bugs Shan Lu, Soyeon Park, Chongfeng Hu, Xiao Ma, Weihang Jiang, Zhenmin Li, Raluca A. Popa, Yuanyuan Zhou. (Zhu Lin on April 30th)
  6. R2: An Application-Level Kernel for Record and Replay. OSDI 2008