Effective Papers

Michael Whittaker , Joe Hellerstein's PhD student at UC Berkeley, has recently defended his PhD thesis on Compartmentalized Paxos . The thesis deconstructs Paxos and shows ways to reconstruct it to be more scalable by individually focusing on each component/role in Paxos. It is a simple but effective trick. Even after you learn the trick, you still keep getting surprised by how effective it is. When I say Michael defended his thesis, I am speaking loosely. Michael was not defensive about anything. He didn't have to be, his work spoke for him. Just watch his PhD presentation and you will understand what I mean.  Michael has a great talent for explaining things simply. Unfortunately this is an underappreciated talent, especially in academia. This may make it look too easy and effortless, and like you didn't do sophisticated work. This dude did not even prepare presentation slides for his PhD thesis (the heresy!), and winged it on the fly by drawing his protocols on an iPad. H...

This is a pun on the saying "there is always room at the top". This is also the title of a famous Feynman lecture from 1959 , where he made a case for nanotechnology.  In this post, I will try to argue that there is plenty of room at the bottom for distributed algorithms. Most work on distributed algorithms are done at a high-level abstraction plane. These high level solutions do not transfer well to the implementation level, and this opens a lot of space to explore at the implementation level. But this is not just an opportunistic argument. It is imperative to target the implementation level with our distributed algorithms work, otherwise they remain as theoretical, unused, inapplicable.  Let me try to demonstrate using consensus protocols as examples. Someone else can make the same case using another subdomain. Be mindful of what is swept under the rug What is succinct at the high level could be very hard to implement and get right at the low level. Paxos seems simple , bu...

This paper has been awarded a best paper award at OSDI20 , and is authored by Mahesh Balakrishnan, Jason Flinn, Chen Shen, Mihir Dharamshi, Ahmed Jafri, Xiao Shi, Santosh Ghosh, Hazem Hassan, Aaryaman Sagar, Rhed Shi, Jingming Liu, Filip Gruszczynski, Xianan Zhang, Huy Hoang, Ahmed Yossef, Francois Richard, and Yee Jiun Song at Facebook, Inc. Delos is the database that stores control plane state for Facebook, building over a shared log system. Each Delos server stores a local copy of a full database, which keeps materialized state of the log, as a Delos table. This DB/ is maintained over the shared log as RSM by just reading commands from the log in sequence and applying them for materializing on the table. Virtual consensus This high level setup is familiar, so let's dive deeper to get to the novelty in this work. Delos uses virtual consensus, which is a fancy way of saying the following. The DB is maintained over a virtual log, which consists of loglets, each of which is implemen...

This paper occurred in VLDB'19 and is authored by Hua Fan and Wojciech Golab.  The paper is about providing strict serializability in geo-replicated databases. The technique it uses can be summarized as "geo-replicate-ahead transactions". First the transaction T is replicated to all the parties across the datacenters. The parties then check to see that the watermark rises above T to ensure that all transactions including and preceding T has been replicated successfully to all the parties. Then, the execution of T can be done asynchronously at each party. This should remind you of the SLOG paper :  SLOG uses a deterministic architecture to move most of this communication outside of conflict boundaries, enabling these transactions to be processed at high throughput. More specifically, SLOG relies on deterministic processing to avoid two phase commit. Once all parties agree to the plan, processing occurs (mostly) independently on each node, with the system relying on the pl...

This paper is from Dan R. K. Ports Jialin Li Vincent Liu Naveen Kr. Sharma Arvind Krishnamurthy (University of Washington) and appeared in NSDI 2015. The previous week, in our Zoom Reading Group , we had read the "Scalable State Machine Replication" paper in our group. SSMR built on top of a "slow" atomic multicast (implemented with Multi-Ring Paxos) and imposed a total order for all messages before SMR.  This paper introduces SpecPaxos (Speculative Paxos), which also tries to impose an ordering of requests messages before SMR processing. SpecPaxos builds on a carefully constructed network to have most messages ordered correctly to start with and provides a way to deal with messages reorderings as needed. The relaxing of the ordering requirement allows Speculative Paxos to achieve good (average) latency and high throughput, and escape the heavy cost of atomic multicast implementation. (To be fair, SpecPaxos doesn't consider the problem of partitioning SMR and...

This paper is by Carlos Eduardo Bezerra, Fernando Pedone, and Robbert van Renesse, and it appeared in DSN 2014.  This paper presents a non-Paxos non-consensus state machine replication (SMR) solution. When I see a non-Paxos solution to SMR, I always ask, "Ok, but where is Paxos hiding here?" It turns out, in this SMR solution, Paxos is hiding in the atomic multicast. The SMR protocol described in the paper assumes atomic multicast feed it. And atomic multicast is a problem equivalent to distributed consensus, and in the evaluation we see that they implement the atomic multicast service using MultiRing Paxos. "Atomic multicast ensures that (i) if a server delivers m, then all correct   servers deliver m (agreement); (ii) if a correct process multicasts m to groups, then all correct servers in every group deliver m (validity); and (iii) relation < is acyclic (order). The order property implies that if s and r deliver messages m and m′, then they deliver them in the sam...

This paper appeared at Eurosys 2020, and is authored by Vitor Enes, Carlos Baquero, Tuanir França Rezende, Alexey Gotsman, Matthieu  Perrin, and Pierre Sutra. The paper introduces Atlas, a consensus protocol similar to EPaxos, that builds on the Fast Paxos idea. Most people call these protocols leaderless, but I think that is a misnomer. I call these protocols as opportunistic/any-leader protocols. In these protocols, any node can propose a command by becoming an opportunistic leader and using a fast path. If there is no other simultaneously proposed command by another opportunistic leader or if this command commutes with all simultaneously proposed commands, the fast path is enough for achieving consensus. In the presence of concurrent non-commuting commands, the protocol will have to take a slow path, the purpose of which is to establish (teach to the other nodes) the dependencies learned for this command in the fast path attempt. This opportunistic/any-leader family of protocols...

I am looking for PhD students to work with me on my project "Paxos Unpacked". I am attaching a short abstract below. The work done here is very useful for distributed databases and cloud computing systems. So if you are interested in a distributed systems PhD, or you know someone interested in a distributed systems PhD, please let me know by emailing me with a short CV and qualifications.  I will have research assistantship funding available for qualifying applicants after they get accepted to the PhD program at University at Buffalo, SUNY. Paxos Unpacked Due to their excellent fault-tolerance properties, Paxos protocols have been employed by many cloud computing systems for consistent coordination of clusters of computers. This project aims to show that when properly customized, Paxos family of protocols can also deliver top-notch performance and scalability, which they currently lack. To this end, the project will design high-performance, scalable, practical, and usable Pax...

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. Instead of ...

This paper is by Sujaya Maiyya, Faisal Nawab, Divyakant Agrawal, and Amr El Abbadi, and appeared in VLDB19. Here is a video of the presentation of the paper from our Zoom DistSys Reading Group. Atomic commitment protocols (e.g., Two Phase Commit) provide ACID guarantees for transactional access to sharded data. Consensus protocols (e.g., Paxos) replicate data across servers in a consistent and fault tolerant manner. Many prior works have observed the similarities between the commitment and consensus problems. Both consensus and atomic commit protocols aim at ensuring that one outcome is agreed upon in a distributed environment. However, the conditions for achieving this agreement is different in the two cases. Paxos only needs a majority of nodes to be available for a decision to be made whereas 2PC needs votes from all the participants to decide on the final value. This paper proposes a framework that unites and explains several commitment and single-leader-based consensus protocols ...

This paper appeared in NSDI'20 and is authored by Cong Ding, David Chu, Evan Zhao, Xiang Li, Lorenzo Alvisi, and Robbert van Renesse. The video presentation of the paper is really nice and gives a good overview of the paper. Here is a video presentation of our discussion of the paper, if that is your learning style, or whatever . (If you like to participate in our paper discussions, you can  join our Slack channel .) Background The problem considered is building a fault-tolerant scalable shared log. One way to do this is to employ a Paxos box for providing order and committing the replication to the corresponding shards. But as the number of clients increase the single Paxos box becomes the bottleneck, and this does not scale. Corfu had the nice idea to divorce ordering and replication. The ordering is done by the Paxos box, i.e., the sequencer, and it assigns unique sequence numbers to the data. Then the replication is offloaded to the clients, which contact the storage se...