CS237 Distributed Systems Middleware

Lecture Notes

Set 1: Middleware and Distributed Systems Introduction

Set 2: Fundamentals: Time, State and Coordination in Distributed Systems

Set 3: Distributed Computing Architectures

Set 4: Messaging Middlewares and Pub/Sub Systems

Set 5: Fault Tolerance in Distributed Systems

Set 6: Early Middleware Frameworks (DCE, Corba, Hadoop)

Set 7: Java-based Technologies

Set 8: Service Oriented Middleware

Set 9: Cloud and Virtualization Platforms

Homeworks

Homework 1: PDF (due Monday, April 18, 2022 at 11:59pm, via Gradescope)

Homework 2: PDF (due Wednesday, May 4, 2022 at 11:59pm, via Gradescope; ignore the due date listed in the PDF)

Homework 3: Paper Summaries from Summary Set 3 (due Wednesday, May 25, 2022 at 11:59pm, via Gradescope)

Homework 4: Paper Summaries from Summary Set 4 (due Monday, June 6, 2022 at 11:59pm, via Gradescope)

Course Reading Materials

How to read a paper:

• How to Read a Paper S. Keshav David R. Cheriton School of Computer Science, University of Waterloo Waterloo, ON, Canada

Reference Books:

• Coulouris et al Distributed Systems: Concepts & Design,4th ed. ISBN: 0-321-26354-5.
• Tanenbaum & van Steen Distributed Systems: Principles and Paradigms, 2nd ed. ISBN: 0-132-39227-5.
• Ben-Ari Principles of Concurrent and Distributed Programming Prentice-Hall International Series in Computer Science, 1990.
• Sape Mullender Distributed Systems Second Edition, Addison-Wesley, 1998. 
• Haggit Attiya and Jennifer Welch Distributed Computing: Fundamentals, Simulations and Advanced Topics
• McGraw Hill, 1998.
• Robert Orfali and Dan Harkey Client/Server Programming with Java and CORBA, Second Edition John Wiley and Sons Inc., 1998

Middleware and Distributed Systems Introduction (NO REVIEW REQUIRED):

1. Middleware David E. Bakken: Encyclopedia of Distributed Computing, Kluwer Academic Publisher.
2. Managing Complexity: Middleware Explained Andrew T. Campbell, Geoff Coulson, and Michael E. Kounavis IT Professional, Vol. 1, No. 5, September/October 1999.
3. Middleware a model for distributed system services Philip A. Bernstein; Commun. ACM 39, 2 (Feb. 1996), Pages 86 - 98
4. An architecture for next generation middleware G. S. Blair, G. Coulson, P. Robin, and M. Papathomas. 2009. In IFIP
5. Fallacies of Distributed Computing Explained  by Arnon Rotem-Gal-Oz

Time, State and Coordination:

1. Lamport, "Time, Clocks and the Ordering of Events in a Distributed System", Communications of the ACM, 1978
2. Mattern, "Virtual Time and Global States of Distributed Systems", Proc. Workshop on Parallel and Distributed Algorithms, 1989
3. M. Chandy and L. Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems", ACM Transactions on Computer Systems, 1985
4. Kshemkalyanit, M. Raynalt and M. Singhals, "An introduction to snapshot algorithms in distributed computing,1999.
5. Raynal M. and Singhal M., Logical time: Capturing causality in distributed systems, Computer, vol. 29, pp. 49-56, 1996.
6. Hunt, Patrick, et al. ZooKeeper: Wait-free Coordination for Internet-scale Systems. USENIX annual technical conference. Vol. 8. No. 9. 2010. 
7. Burrows, Mike.The Chubby lock service for loosely-coupled distributed systems. Proceedings of the 7th symposium on Operating systems design and implementation. 2006.

 

Recent Systems:

8. Lakshman, Avinash, and Prashant Malik. "Cassandra: a decentralized structured storage system.", ACM SIGOPS Operating Systems Review 44.2 (2010): 35-40.
9. Corbett, James C., et al. "Spanner: Google’s globally distributed database.", ACM Transactions on Computer Systems (TOCS) 31.3 (2013): 1-22.
10. Gao, Roshan Sumbaly Jay Kreps Lei, and Alex Feinberg Chinmay Soman Sam Shah. "Serving Large-scale Batch Computed Data with Project Voldemort."

 

Additional Papers:

11. Cristian and C. Fetzer, "Fault-tolerant external clock synchronization", ICDCS 1995
12. C.l Fidge, Timestamps in message-passing systems that preserve the partial ordering , Australian Computer Sci. Comm. 10 (I) (February 1988) 56-66.
13. C.l Fidge, Fundamentals of distributed system observation, IEEE Software 13 (6) (November 1996) 77-83.
14. C.l Fidge, A limitation of vector timestamps for reconstructing distributed computations, in: Elsevier Science, 1998, Information Processing Letters 87-91.
15. Schwarz, R. and Mattern, F. "Detecting causal relationships in distributed computations, Distributed Computing, 1994.

 

1. Y. Chawathe, S. Ratnaswamy, L. Breslau, N. Lanham, S. Shenker, "Making Gnutella-like P2P Systems Scalable", ACM Sigcomm 2003
2. Daniel Stutzbach, Reza Rejaie, and Subhabrata Sen, "Characterizing Unstructured Overlay Topologies in Modern P2P File-Sharing Systems", Networking, 2008. (Gnutella related)
3. Dongyu Qiu and R. Srikant, "Modeling and performance analysis of BitTorrent-like peer-to-peer networks", Proceedings of ACM Sigcomm, 2004.
4. I. Stoica, R. Morris, D. Karger, M. Frans Kaashoek, H.Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications", Proc. ACM Sigcomm, August 2001.
5. S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker, "A Scalable Content-Addressable Network", Proceedings of ACM Sigcomm, August, 2001.
6. A. Rowstron, P. Druschel, "Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems", IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), November, 2001.
7. J Kubiatowicz, "OceanStore: an architecture for global-scale persistent storage", SIGPLAN 2000
8. DeCandia, Giuseppe, et al. "Dynamo: amazon's highly available key-value store.", ACM SIGOPS 2007.
9. Qin Lv, Pei Cao, Edith Cohen, Kai Li, and Scott Shenker, "Search and Replication in Unstructured Peer-to-Peer Networks", 16th international conference on Supercomputing. 2002.
10. Mishra, Asit K., et al. "Towards Characterizing Cloud Backend Workloads: Insights from Google Compute Clusters.", ACM SIGMETRICS 2010.
11. Liu, Yang, Jogesh K. Muppala, and Malathi Veeraraghavan. "A survey of data center network architectures.", 2014.
12. Satyanarayanan, Mahadev. "The emergence of edge computing.", Computer 50.1, 2017.
13. Karger, David, et al."Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web.", 29th ACM symposium on Theory of computing. 1997.

Messaging Middlewares, Pub/Sub Systems (SUMMARY SET 3):

1. Banavar, Guruduth, et al. "A Case for Message Oriented Middleware", International Symposium on Distributed Computing 1999
2. Fabret, Françoise, et al. "Filtering algorithms and implementation for very fast publish/subscribe systems.", SIGMOD 2001
3. Banerjee, B. Bhattacharjee and C. Kommareddy, "Scalable Application Layer Multicast", ACM SIGCOMM 2002
4. Castro, Miguel, et al. "SCRIBE: A large-scale and decentralized application-level multicast infrastructure", 2002
5. Pietzuch, Peter R., and Jean M. Bacon. "Hermes: A distributed event-based middleware architecture", ICDCSW 2002
6. Eugster, Patrick Th, et al. "The Many Faces of Publish/Subscribe", ACM computing surveys 2003
7. Jacobsen, Hans-Arno, et al. "The PADRES publish/subscribe system.", 2006
8. Jacobsen, Hans-Arno, et al. "Content-based publish-subscribe over structured overlay networks", ICDCS 2005
9. Chockler, Gregory, et al. "Spidercast: a scalable interest-aware overlay for topic-based pub/sub communication", DEBS 2007
10. Setty, Vinay, et al. "Poldercast: Fast, robust, and scalable architecture for P2P topic-based pub/sub" ACM International Conference on Distributed Systems Platforms and Open Distributed Processing 2012
11. Hojjat Jafarpour, Bijit Hore, Sharad Mehrotra and Nalini Venkatasubramanian. "CCD: Efficient Customized Content Dissemination in Distributed Publish/Subscribe.", Middleware 2009
12. Hojjat Jafarpour, Sharad Mehrotra and Nalini Venkatasubramanian. " A Fast and Robust Content-based Publish/Subscribe Architecture", IEEE NCA 2008
13. Kreps, Jay, Neha Narkhede, and Jun Rao. "Kafka: A distributed messaging system for log processing.", Proceedings of the NetDB 2011
14. Carbone, Paris, et al. "Apache flink: Stream and batch processing in a single engine", Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 2015
15. M. Y. S. Uddin, and N. Venkatasubramanian. "Edge Caching for Enriched Notifications Delivery in Big Active Data", ICDCS 2018
16. Destounis, Apostolos, Georgios S. Paschos, and Iordanis Koutsopoulos. "Streaming big data meets backpressure in distributed network computation", INFOCOM 2016
17. Tatbul, Nesime, Uǧur Çetintemel, and Stan Zdonik. "Staying fit: Efficient load shedding techniques for distributed stream processing", Proceedings of the 33rd international conference on Very large data bases 2007

 

Additional Papers:

18. Pardo-Castellote, Gerardo. "Omg data-distribution service: Architectural overview.", ICDCSW 2003
19. Object Management Group Data Distribution Service™
20. Apache Pulsar
21. Apache Storm

Time, State and Coordination:

1. Lamport, "Time, Clocks and the Ordering of Events in a Distributed System", Communications of the ACM, 1978
2. Mattern, "Virtual Time and Global States of Distributed Systems", Proc. Workshop on Parallel and Distributed Algorithms, 1989
3. M. Chandy and L. Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems", ACM Transactions on Computer Systems, 1985
4. Kshemkalyanit, M. Raynalt and M. Singhals, "An introduction to snapshot algorithms in distributed computing,1999.
5. Raynal M. and Singhal M., Logical time: Capturing causality in distributed systems, Computer, vol. 29, pp. 49-56, 1996.
6. Hunt, Patrick, et al. ZooKeeper: Wait-free Coordination for Internet-scale Systems. USENIX annual technical conference. Vol. 8. No. 9. 2010. 
7. Burrows, Mike.The Chubby lock service for loosely-coupled distributed systems. Proceedings of the 7th symposium on Operating systems design and implementation. 2006.

 

Recent Systems:

8. Lakshman, Avinash, and Prashant Malik. "Cassandra: a decentralized structured storage system.", ACM SIGOPS Operating Systems Review 44.2 (2010): 35-40.
9. Corbett, James C., et al. "Spanner: Google’s globally distributed database.", ACM Transactions on Computer Systems (TOCS) 31.3 (2013): 1-22.
10. Gao, Roshan Sumbaly Jay Kreps Lei, and Alex Feinberg Chinmay Soman Sam Shah. "Serving Large-scale Batch Computed Data with Project Voldemort."

 

Additional Papers:

11. Cristian and C. Fetzer, "Fault-tolerant external clock synchronization", ICDCS 1995
12. C.l Fidge, Timestamps in message-passing systems that preserve the partial ordering , Australian Computer Sci. Comm. 10 (I) (February 1988) 56-66.
13. C.l Fidge, Fundamentals of distributed system observation, IEEE Software 13 (6) (November 1996) 77-83.
14. C.l Fidge, A limitation of vector timestamps for reconstructing distributed computations, in: Elsevier Science, 1998, Information Processing Letters 87-91.
15. Schwarz, R. and Mattern, F. "Detecting causal relationships in distributed computations, Distributed Computing, 1994.

 

Fault Tolerance and Reliability :

 Consensus

16. J. Fischer, N. A. Lynch, and M. S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of ACM, 1985
17. Dolev, C. Dwork, L. Stockmeyer, "On the Minimal Synchronism Needed for Distributed Consensus", Journal of ACM, 1987.
18. Lamport, Leslie, "Paxos made simple", ACM Sigact News 32.4 (2001).
19. Ongaro, Diego, and John Ousterhout, "In search of an understandable consensus algorithm", 2014 USENIX Annual Technical Conference. --- RAFT ---
20. Howard, Heidi, and Richard Mortier. "Paxos vs Raft: Have we reached consensus on distributed consensus? ", Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data. 2020

 

 Failure Detectors

21. D. Chandra and S. Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems", Journal of ACM, 1985
22. D. Chandra, V. Hadzilacos and S. Toueg, "The Weakest Failure Detector for Solving Consensus", Journal of ACM, 1996
23. K. Aguilera, W. Chen, and S. Toueg, "Heartbeat: A Timeout-Free Failure Detector for Quiescent Reliable Communication", Cornel, 1997

 

 Replication

24. S. Sandhu and S. Zhou, "Cluster-based file replication in large-scale distributed systems", ACM SIGMETRICS, 1992
25. Gray, P. Helland, P. Neil and D. Shasha , "The dangers of replication and a solution", ACM SIGMOD, 1996

 

 Logging

26. P. Sistla and J. L. Welch, "Efficient distributed recovery using message logging", ACM SIOPS, 1989