My Distributed Systems Seminar reading list for Spring 2015

-

Below is the list of papers I plan to discuss in my distributed systems seminar this semester. If you have some suggestions on other good/recent papers to cover, please let me know in the comments.
  1. Perspectives on the CAP Theorem
  2. Consistency, availability, and convergence.
  3. Salt: combining ACID and BASE in a distributed database
  4. Extracting More Concurrency from Distributed Transactions
  5. Eidetic Systems
  6. Simple Testing Can Prevent Most Critical Failures: An Analysis of Production Failures in Distributed Data-Intensive Systems
  7. The Mystery Machine: End-to-end Performance Analysis of Large-scale Internet Services
  8. All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications
  9. GraphX: Graph Processing in a Distributed Dataflow Framework
  10. Architecture of a database system
  11. Arrakis: The Operating System is the Control Plane
  12. Fast Databases with Fast Durability and Recovery Through Multicore Parallelism
  13. Project Adam: Building an Efficient and Scalable Deep Learning Training System


Comments

Timothy Chen said…
Really nice set of papers! Is the seminar videos going to be available online for non-students?
February 12, 2015 at 6:42 PM
Post a Comment

Popular posts from this blog

Learning about distributed systems: where to start?

-
This is definitely not a "learn distributed systems in 21 days" post. I recommend a principled, from the foundations-up, studying of distributed systems, which will take a good three months in the first pass, and many more months to build competence after that. If you are practical and coding oriented you may not like my advice much. You may object saying, "Shouldn't I learn distributed systems with coding and hands on? Why can I not get started by deploying a Hadoop cluster, or studying the Raft code." I think that is the wrong way to go about learning distributed systems, because seeing similar code and programming language constructs will make you think this is familiar territory, and will give you a false sense of security. But, nothing can be further from the truth. Distributed systems need radically different software than centralized systems do.  --A. Tannenbaum This quotation is literally the first sentence in my distributed systems syllabus. Inst
Read more >>

Hints for Distributed Systems Design

-
This is with apologies to Butler Lampson, who published the " Hints for computer system design " paper 40 years ago in SOSP'83. I don't claim to match that work of course. I just thought I could draft this post to organize my thinking about designing distributed systems and get feedback from others. I start with the same  disclaimer Lampson gave. These hints are not novel, not foolproof recipes, not laws of design, not precisely formulated, and not always appropriate. They are just hints.  They are context dependent, and some of them may be controversial. That being said, I have seen these hints successfully applied in distributed systems design throughout my 25 years in the field, starting from the theory of distributed systems (98-01), immersing into the practice of wireless sensor networks (01-11), and working on cloud computing systems both in the academia and industry ever since. These heuristic principles have been applied knowingly or unknowingly and has proven
Read more >>

Foundational distributed systems papers

-
I talked about the importance of reading foundational papers last week. To followup, here is my compilation of foundational papers in the distributed systems area. (I focused on the core distributed systems area, and did not cover networking, security, distributed ledgers, verification work etc. I even left out distributed transactions, I hope to cover them at a later date.)  I classified the papers by subject, and listed them in chronological order. I also listed expository papers and blog posts at the end of each section. Time and State in Distributed Systems Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport, Commn. of the ACM,  1978. Distributed Snapshots: Determining Global States of a Distributed System. K. Mani Chandy Leslie Lamport, ACM Transactions on Computer Systems, 1985. Virtual Time and Global States of Distributed Systems.  Mattern, F. 1988. Practical uses of synchronized clocks in distributed systems. B. Liskov, 1991. Expository papers
Read more >>

Metastable failures in the wild

-
Image
This paper appeared in OSDI'22. There is a great summary of the paper by Aleksey (one of the authors and my former PhD student, go Aleksey!). There is also a great conference presentation video from Lexiang. Below I will provide a brief overview of the paper followed by my discussion points. This topic is very interesting and important, so I hope you have fun learning about this. Metastability concept and categories Metastable failure is defined as permanent overload with low throughput even after the fault-trigger is removed. It is an emergent behavior of a system, and it naturally arises from the optimizations for the common case that lead to sustained work amplification. In this paper, the authors are able to capture/abstract the system behavior of interest in terms of two parameters, the load and capacity. If the load is above capacity, you have work piling up, right? Or if the capacity drops under the sustained load level, the same effect, right? Both of these create  a tem
Read more >>

Scalable OLTP in the Cloud: What’s the BIG DEAL?

-
Image
This paper is from Pat Helland, the apostate philosopher of database systems, overall a superb person, and a good friend of mine. The paper appeared this week at CIDR'24. (Check out the program for other interesting papers). The motivating question behind this work is: " What are the asymptotic limits to scale for cloud OLTP (OnLine Transaction Processing) systems? " Pat says that the CIDR 2023 paper "Is Scalable OLTP in the Cloud a Solved Problem?" prompted this question.  The answer to the question? Pat says that the answer lies in the joint responsibility of database and the application. If you know of Pat's work, which I have summarized several in this blog , you would know that Pat has been advocating along these lines before. But this paper provides a very crisp, specific, concrete answer. Read on for my summary of the paper. Disclaimer: This is a wisdom and technical information/detail packed 13-page paper, so I will try my best to summarize the sa
Read more >>

Understanding the Performance Implications of Storage-Disaggregated Databases

-
Image
Storage-compute disaggregation in databases has emerged as a pivotal architecture in cloud environments, as evidenced by Amazon ( Aurora ), Microsoft ( Socrates ), Google (AlloyDB), Alibaba ( PolarDB ), and Huawei (Taurus). This approach decouples compute from storage, allowing for independent and elastic scaling of compute and storage resources. It provides fault-tolerance at the storage level. You can then share the storage for other services, such as adding read-only replicas for the databases. You can even use the storage level for easier sharding of your database. Finally, you can also use this for exporting a changelog asynchronously to feed into peripheral cloud services, such as analytics. Disaggregated architecture was the topic of Sigmod 23 panel . I think this quote summarizes the industry's thinking on the topic. "Disaggregated architecture is here, and is not going anywhere. In a disaggregated architecture, storage is fungable, and computing scales independently.
Read more >>

Always Measure One Level Deeper

-
Image
This is a great paper (CACM 2018) by John Ousterhout. Ousterhout is well known for his work on log-structured file system, tcl/tk, Raft, and magic VLSI CAD. His book on Philosophy of Software Design is great, and he has a lot of wisdom about life in general that he shares in his Stanford CS classes. The paper is written very well, so I lift up paragraphs verbatim from it to summarize its main points. There are many war stories in the text. Please do read it, because they are fascinating, and likely you can see how they can apply to your work, and save you from making a mistake. At the end, I chime in with my reflections and link to other relevant work.  Key Insights In academic research a thorough performance evaluation is considered essential for many publications to prove the value of a new idea. In industry, performance evaluation is necessary to maintain a high level of performance across the lifetime of a product. A good performance evaluation provides a deep understanding of
Read more >>

The end of a myth: Distributed transactions can scale

-
Image
This paper appeared in VLDB'17. The paper presents NAM-DB, a scalable distributed database system that uses RDMA (mostly 1-way RDMA) and a novel timestamp oracle to support snapshot isolation (SI) transactions. NAM stands for network-attached-memory architecture, which leverages RDMA to enable compute nodes talk directly to a pool of memory nodes. Remote direct memory access (RDMA) allows bypassing the CPU when transferring data from one machine to another. This helps relieve a major factor in scalability of distributed transactions: the CPU overhead of the TCP/IP stack. With so many messages to process, CPU may spend most of the time serializing/deserializing network messages, leaving little room for the actual work. We had seen this phenomena first hand when we were researching the performance bottlenecks of Paxos protocols. This paper reminds me of the "Is Scalable OLTP in the Cloud a Solved Problem? (CIDR 2023)" which we reviewed recently. The two papers share one
Read more >>

Dude, where's my Emacs?

-
It had been 3 years since I had to setup a new laptop. Past Murat had left me helpful instructions , but I got a bad surprise while configuring my Emacs setup. My beloved starter-kits, which worked smoothly under Emacs 27, stopped working under Emacs 29. I tried to fix the errors, but this proved futile due to my limited elisp/emacs skills.  I explored alternative starter-kits to configure Emacs. Doom emerged as the dominant choice, but it appeared large, bloated, and complex for my liking. I tried a couple small starter kits, but I faced other problems and was unable to integrate my customizations and get to a reasonable setup.  I am an Emacs user for 25 years, and I know a thing or two, but it seems everyone's now an Emacs pro. I don't get how people are able to accept and work with those complicated config files/directories. I started to speculate. Maybe the ordinary users left, leaving behind the proficient Emacs enthusiasts, who kept writing more and more intricate confi
Read more >>

Know Yourself

-
MongoDB has a nice leadership development program internally. They suggested that filling/sharing this questionnaire would be useful to get you acquainted with the people you work with daily. I am not super into being in-touch with your feelings stuff, so I thought I probably won't do this. But then, the questions were interesting, and I jot down my answers to them quickly. I don't think this took me more than 5 minutes or so, and I felt good after having answered the questions. Maybe this gave me a little bit of self-acceptance, and being kind to my innate nature rather than judging it all the time. The questionnaire description was spot on: "Increase awareness of your own preferences by answering the questions below." Here are my answers to these questions. What would your answers be? I think it is good practice to do this exercise once in a while to know yourself a bit better. What are you AMAZING at? Where do you want to improve? I am good at research. I enjoy bei
Read more >>