Advanced Distributed Systems

Fall 2007

General Course Information:

Instructor: Lakshmish Ramaswamy (laks[AT]cs[dot]uga[dot]edu, 706-542-2737)
 
Time and Venue(Tentative): Wednesdays - 3:35 PM to 4:25 PM; Tuesdays & Thursdays - 03:30 PM to 04:45 PM
 
Office Hours: To be announced

Course Description:

Distributed systems have become widely pervasive and are having a tremendous impact on various domains of human activity. Today's distributed systems range from ad-hoc networks comprising of tiny sensor devices, to overlay networks such as peer-to-peer systems, to massive web farms of powerful servers. The research in the area of distributed systems has focused on achieving better performance, reliability, security, and privacy of various kinds of distributed data processing applications.

In this course we will study the design, implementation and evaluation of a wide class of distributed systems including edge cache networks, multimedia content distribution networks, peer-to-peer systems, publish-subscribe systems, stream processing systems, mobile systems and sensor networks, with the objective of gaining an in-depth understanding of the requirements and the design options.

Grading Policy (Tentative)

Course Materials (Tentative)

Web content generation and delivery
(Preliminary study: AFS and NFS in Silbershatz, Galvin and Gagne "OS Concepts [Chapter 11])
  1. Nelson, M.N., Wlech, B.B., Ousterhout, J.K., "Caching in the Sprite Network File System", ACM Transactions on Computer Systems, 6, 1, pgs. 134-154, February 1988. (self-study)
  2. Anderson, T. et. al, "Serverless Network File System", ACM Transpaction on Computer Systems, February 1996.
  3. C. Thekkath, T. Mann and E. Lee "Frangipani: A Scalable Distributed File System",  (SOSP), October 1997.
  4. C. Amza, A. Cox, S Dwarkadas, P Keleher, H Lu, R. Rajamony, W. Yu and W. Zwaenepoel, "TreadMarks: Shared Memory Computing on Networks of Workstations" IEEE Computer, February, 1996.
Web content generation and delivery
   
    Web servers and application servers
  1. N. J. Yeager, R. E. McGrath "Web Server Technology", Morgan Kaufmann
  2. A. Iyengar, J. Challenger, D. Dias, and P. Dantzig. High-Performance Web Site Design Techniques. IEEE Internet Computing, 4(2):17--26, March 2000.
  3. J. Challenger, P. Dantzig, A. Iyengar "A Scalable and Highly Available System for Serving Dynamic Data at Frequently Accessed Web Sites", Supercomputing - 98
  4. G. Banga and P.Druschel " Measuring the Capacity of a Web Server", USENIX Symposium on Internet Technologies and Systems - 1997
  5. Arlitt and Williamson " Internet Web Servers: Workload Characterization and Performance Implications", ACM/IEEE Transactions on Networking, October 1997
  6. V. N. Padmanabhan and L. Qiu,  "The Content and Access Dynamics of a Busy Web Site: Findings and Implications", ACM-SIGCOMM 2000
  7. A. Iyengar, M. S. Squillante, L. Zhang "Analysis and Characterization of Large-Scale Web Server Access Patterns and Performance" World Wide Web Journal-1999
            Web Content Caching and Delivery
    1. A. Chankhunthod, P. Danzig, C. Neerdaels, M. F. Schwartz, K. J. Worrell. A Hierarchical Internet Object Cache USENIX Annual Technical Conference,  1995 
    2. R. Tewari, M. Dahlin, H. M. Vin, J. S. Kay. Beyond Hierarchies: Design Considerations for Distributed Caching on the Internet, ICDCS 1999 
    3. L. Fan, P. Cao, J. Almeida, A. Z. Broder. Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol, IEEE/ACM Transactions on Networking, 2000 
    4. J. Yin, L. Alvisi, M. Dahlin, A. Iyengar. Engineering Server-Driven Consistency for Large Scale Dynamic Web Services, WWW conference, 2001 
    5. K. Amiri, S. Park, R. Tewari and S. Padmanabhan. DBProxy: A dynamic data cache for Web applications, ICDE 2003 
    6. WS Li, O Po, WP Hsiung, KS Candan, D Agrawal. Engineering and hosting adaptive freshness-sensitive web applications on data centers, WWW Conference 2003
    7. S Shah, K Ramamritham, P Shenoy. Resilient and Coherence Preserving Dissemination of Dynamic Data Using Cooperating Peers IEEE TKDE 2004.
    8. L. Ramaswamy, A. Iyenagar, L. Liu and F. Douglis, Automatic Detection of Fragments in Dynamic Web Pages and its Impact on Caching, IEEE TKDE 2005 
    9. L. Ramaswamy, L. Liu and Arun Iyengar  Cooperative EC Grid: Caching Dynamic Documents using Cache Clouds (Hard copies will be provided in the class) 
    10.  C. Yuan, Y. Chen and Z. Zhang, Evaluation of edge caching/offloading for dynamic content delivery. WWW 2003

     Peer -to-Peer Computing and Overlay Networks

    1. S. Androutsellis-Theotokis and D. Spinellis A Survey of Peer-to-Peer File Sharing Technologies, ACM Computing Surveys 2002. 
    2. Jordan Ritter, Why Gnutella Can't Scale. No, Really. 2001 
    3. B. Yang, H. Garcia-Molina, Improving Search in Peer-to-Peer Networks, ICDCS 2002
    4. LV, C., CAO, P., COHEN, E., LI, K., AND SHENKER, S. Search and replication in unstructured peer-to-peer networks, Supercomputing 2002
    5. M. Ripeanu, I. T. Foster, A. Iamnitchi,  Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design, IEEE Internet Computing Journal, 2002
    6. Q. Lv, S. Ratnasamy and S. Shenker Can Heterogeneity Make Gnutella Scalable, IPTPS 2002
    7. K. Gummadi, R. J. Dunn, S. Saroiu, S. D. Gribble, H. M. Levy and Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload. SOSP 2003
    8. CHAWATHE, Y., RATNASAMY, S., BRESLAU, L., AND SHENKER, S. Making Gnutella-like P2P Systems Scalable, SIGCOMM-2003
    9. E. Cohen and S. Shenker, Replication strategies in unstructured peer-to-peer networks. SIGCOMM 2002
    10. I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. Kaashoek, F. Dabek and H. Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications, IEEE/ACM Transactions on Networking, February 2003
    11. A. Rowstron and P. Druschel, Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems, Middleware 2001 
    12. Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp and Scott Shenker, A Scalable Content-Addressable Network, SIGCOMM 2001 
    13. Karl Aberer, Philippe Cudré-Mauroux, Anwitaman Datta, Zoran Despotovic, Manfred Hauswirth, Magdalena Punceva, Roman Schmidt  P-Grid: A Self-organizing Structured P2P System, SIGMOD RECORD 2003 
    14. S. C. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica, and H. Yu. OpenDHT: A public DHT service and its uses, SIGCOMM 2005 
    15. Y. Chawathe, S. Ramabhadran, S. Ratnasamy, A. LaMarca, S. Shenker, J. Hellerstein, A Case Study in Building Layered DHT Applications, SIGCOMM 2005 
    16. A. Rao K. Lakshminarayanan S. Surana R. Karp I. Stoica Load Balancing in Structured P2P Systems, INFOCOM 2003 
    17. A. R. Bharambe, M. Agrawal, and S. Seshan, Mercury: supporting scalable multi-attribute range queries,  SIGCOMM 2004 
    18. Dongsheng Li, Jiannong Cao, Xicheng Lu, Keith C. C. Chan, Jinshu Su, H.V. Leong, Alvin T. S. Chan , Delay-Bounded Range Queries in DHT-based Peer-to-Peer Systems, ICDCS 2006 (Copies provided in class) 
    19. P. B. Godfrey, S. Shenker, and I. Stoica, Minimizing Churn in Distributed Systems, SIGCOMM 2006. 
    20. J. Kannan,  B. Yang, S. Shenker, P. Sharma, S. Banerjee, S. Basu, S.J. Lee, SmartSeer: Using a DHT to Process Continuous Queries Over Peer-to-Peer Networks, INFOCOM 2006
    21. V. Pappas, D. Massey, A. Terzis and L. Zhang, A Comparative Study of Current DNS with DHT-Based Alternatives, INFOCOM 2006   
    Event Processing and Publish/Subscribe Systems
    1. P. Th. Eugster, P. A. Felber, R. Guerraoui and A.-M. Kermarrec, The Many Faces of Publish-Subscribe, ACM Computing Surveys, 2003.
    2. G. Banavar, T. Chandra, B. Mukherjee, J. Nagarajarao, R. Strom and D. Sturman, An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems, ICDCS 1999.
    3. L. Ramaswamy, J. Chen and P. Parate, COQUOS: Lightweight Support to Continuous Queries on Unstructured Overlays, IPDPS 2007
    4. A. Carzaniga, D. S. Rosenblum and A. Wolf, Design and Evaluation of a Wide-Area Event Notification Service ACM TOCS 2001
    5. A. Gupta, O. Sahin, D. Agrawal and A. El Abbadi Meghdoot: Content-based Pub/Sub over P2P Networks Middleware 2004
    6. P.A. Chirita, S. Idreos, M. Kaubarakis and W. Nejdl Designing Semantics Pub/Sub Using Super Peers, Middleware 2005
    7. Y. Huang and H. Garcia-Molina Publish-Subscribe in a Mobile Environment, Wireless Networks, 2004.
    8. S. Banerjee, S. Basu, J. Kannan, S. J. Lee, P. Sharma, S. Shenker, and B. Yang, SmartSeer: Using a DHT to Process Continuous Queries Over Peer-To-Peer Networks, INFOCOM 2006
Stream Processing,
  1.  S. Babu and J. Widom, "Continuous Queries over Data Streams", SIGMOD Record 2001
  2. S. Chandrasekaran, M. J. Franklin: Streaming Queries over Streaming Data. VLDB 2002
  3. S. Madden, M. J. Franklin: Fjording the Stream: An Architecture for Queries Over Streaming Sensor Data. ICDE 2002
  4. D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. Zdonik. Monitoring Streams: A New Class of Data Management Applications, VLDB 2002
  5. S. Chandrasekaran, et al. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. CIDR 2003
  6. M. Cherniack, H. Balakrishnan, M. Balazinska, D. Carney, U. Cetintemel, Y. Xing, S. Zdonik, Scalable Distributed Stream Processing, CIDR 2003
  7. D. J. Abadi, et al. The Design of the Borealis Stream Processing Engine CIDR-2005 
  8. M.J. Stonebraker, U. Cetintemel, and S. Zdonik, The 8 Requirements of Real-Time Stream Processing  ICDE 2005
  9. M. Balazinska, H. Balakrishnan, S. Madden, and M.Stonebraker, Fault-Tolerance in the Borealis Distributed Stream Processing System, SIGMOD 2005 
  10.  P.R. Pietzuch, et al. Network-Aware Operator Placement for Stream-Processing Systems, ICDE 2006
  11. N. Tatbul, S. Zdonik,  Window-aware Load Shedding for Aggregation Queries over Data Streams, VLDB 2006
Security and Privacy
    1. M. Srivatsa and L. Liu, "Securing Publish-Subscribe Overlay Services With EventGuard" ,  ACM CCS 2005
    2. M. Srivatsa, L. Xiong and L. Liu, "TrustGuard: Countering Vulnerabilities in Reputation Management for Decentralized Overlay Networks" WWW 2005.
    3. L. Sweeney, k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems. 
    4. K. LeFevre, D. DeWitt, and R. Ramakrishnan. Incognito: Efficient Full-Domain K-Anonymity. In ACM SIGMOD 2005.
    5. A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-Diversity: Privacy Beyond k-Anonymity. ICDE-2006.

Presentation Slides


Miscellanious Materials