Effective Papers

This paper appeared in PODC 2019, and is by Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham.  The paper presents HotStuff, a leader-based Byzantine fault-tolerant consensus protocol. HotStuff forms the basis of LibraBFT which is used in Facebook's Libra project. HotStuff uses the partially synchronous model for liveness, but it is safe even under an asynchronous model. (This is also how Paxos operates, as a crash tolerant consensus protocol.) Once network communication becomes synchronous, HotStuff enables a correct leader to drive the protocol to consensus at the pace of actual (vs. maximum) round duration --a property called responsiveness . Another innovation in HotStuff is that it provides communication complexity that is linear  (rather than quadratic) in the number of replicas. In other words, all-to-all broadcasts are replaced with only participant-to-leader and leader-to-participant communication, with rotating leaders. HotStuff is the ...

This paper appeared in VLDB'19 and is authored by Maurice Herlihy, Barbara Liskov, and Liuba Shrira. How can autonomous, mutually-distrusting parties cooperate safely and effectively? This question is very important for enabling commerce. The trading world answered this question so far by relying on a trusted third party, and in the worst case, on the government/rule-of-law to litigate parties deviating from their contracts. With prevalence of e-commerce and decentralization, this question is recently  considered in *trustless* settings by modern distributed data management systems. Solving the trustless multi-party cooperation when all the parties use the same blockchain is achievable via smartcontracts, but solving the problem where the parties use different blockchains bring many additional challenges. Some of these challenges are familiar to us from the classical distributed systems research on distributed transactions, such as how to combine multiple steps into a single atomic...

We are entering 2020, and this is a good time to retrospect and review the past decade from the lens of this blog, which started late 2010. I started posting regularly on September 2010. I wanted to get into the cloud computing domain, so I needed to accumulate background on cloud computing work. I decided that as I read papers on cloud computing, I will post a summary to this blog. I thought if I could explain what I learned from the papers in my own words, I would internalize those lessons better. And if others read those summaries and benefit, that is an extra plus. Initially I reviewed and posted paper summaries on big data processing systems and NoSQL distributed databases to catch up on these areas. Around 2010s, misrepresentation of the CAP theorem by NoSQL proponents was a problematic issue. I covered some papers that try to clarify this issue. Throughout the years, I covered many papers that discussed the different consistency guarantees offered by distributed databases. Tr...

Below is the first draft list of papers I plan to discuss in my distributed systems seminar in the Spring semester. If you have some suggestions on some good/recent papers to cover, please let me know. Paxos Canopus: A Scalable and Massively Parallel Consensus Protocol  (CoNext17)  Consus taming the Paxi   Stable and consistent membership at scale with rapid  (ATC18) Unifying consensus and atomic commit  (VLDB19)  Wormspace: A modular foundation for simple, verifiable distributed systems  (SOCC19)  Replication Mergeable replicated data types  (OOPSLA19)  Exploiting Commutativity For Practical Fast Replication  (NSDI19)  Amazon Aurora: On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes  (SIGMOD18)  Dynamic atomic storage without consensus (JACM 2011)  PaxosStore:  High-availability Storage Made Practical in WeChat  (VLDB17) Transactions/consistency Interactive checks for coordin...

In PODC 1983, Michael Ben-Or published a randomized distributed asynchronous consensus algorithm in a paper titled "Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols" . After 15 years, a paper in 1998 provided a correctness proof of Ben-Or's algorithm . Above is the pseudocode for Ben-Or from that paper. From the pseudocode it looks like Ben-Or is a very simple algorithm, but in reality its behavior is not easy to understand and appreciate. But fret not, TLA+ modeling and model checking helps a lot for understanding the behavior of the Ben-Or algorithm. It is fulfilling when you finally understand how the algorithm works, and how safety is always preserved and progress is achieved eventually probabilistically. I had assigned modeling of Ben-Or as the TLA+ project for my distributed systems class . Here I share my PlusCal modeling of Ben-Or, and discuss how this model helps us to understand the algorithm better. Here is the l...

This is a followup to my "Master Your Questioning Skills" post. There I gave some suggestions about how to ask better questions, but didn't engage with the topic directly. Coming up with the questions is not difficult, once you get out of your default mode and give yourself the license to indulge in the questioning frame of mind.  By calling these questions MAD questions, I gave myself the license/protection to go wild, uninhibited by traditional assumptions/constraints. This gave rise to reducing the bar, and approaching the topic with a beginner mind, as an outsider. This made it easier to ask more original questions. By detaching and discarding the baggage of tradition, you can start working from the first principles.  To get to the good questions, get over with the bad questions. Bad questions lead to good questions. So roll with them and exhaust them to get to the good questions.  A good question gives you a perspective change that is productive. It opens a new area...

"Moneyball: The Art of Winning an Unfair Game" is a book by Michael Lewis, published in 2003, about the Oakland Athletics baseball team and its general manager Billy Beane. Its focus is the team's analytical, evidence-based, sabermetric approach to assembling a competitive baseball team despite Oakland's small budget.  I had zero knowledge and interest about baseball, but the book was very engaging, and I could stop reading. Michael Lewis is one of my favorite writers. I had read Flash Boys, Big Short , and Next by him, and all of them were very good. Fundamentally, Moneyball is about making radical but rational choices to the face of flawed ways of the tradition. Where there is a tradition-ridden unoptimized market, there is potential for disruption: if you are brave enough to do things differently, you can benefit a lot from doing so.  Initially only a few people are daring enough to see this and ignore the tradition and status-quo to start doing things differently...