Metadata

I finished listening to this book 10 days ago. I liked this book a lot while listening to it. Now, I am having second thoughts. The book uses the Bhagavad Gita (a 700-verse Hindu scripture dated to the second century BCE) as a source/starting point to dispense advice about how to have a fulfilling life and career. The Gita is a dialogue between Krishna and Arjuna right before the start of the climactic Kurukshetra War in the Hindu epic Mahabharata. Two massive armies have gathered to destroy the other. The Pandava prince Arjuna asks his charioteer Krishna to drive to the center of the battlefield so that he can get a good look at both the armies and all those "so eager for war". He sees that some among his enemies are his own relatives, beloved friends, and revered teachers. He does not want to fight to kill them and is thus filled with doubt and despair on the battlefield. He drops his bow, wonders if he should renounce and just leave the battlefield. He turns to his chari...

This post is a sequel to my last two posts on Streamlet. The first one explained the protocol . The second one presented a first draft modeling of the protocol. In this post, I present two improvements to the first draft modeling.  In the first, I will make the epochs monotonic at the process level. In the second one, I give each node its own inbox, instead of using a shared whiteboard message set. Again, I will introduce the model dev-log style, using the notes I took while developing it. Adding locally monotonic epochs Why don't I just sequentially increase e in the process main loop. Instead of using while true, with e \in E, the process will go through the epochs in increasing order. This still doesn't constrain the processes to go in lock-step through the epochs. Each process can go through epochs in its own pace independent of the others. The only requirement is if a process participated at an epoch (either as a proposer or voter), it will not participate at a lower epoch...

I had provided an overview of the Streamlet blockchain protocol in my last post , please read that before reading this post on modeling Streamlet in TLA+. Also if you want to get an idea about TLA+, this may be a good post to read. Here I model the crash fault-tolerant version of Streamlet provided in Appendix A of the paper. Modeling Byzantine nodes is very hard: How do you simulate arbitrary behavior of the nodes? How do you then hope to model check it? So I stick with the crash fault-tolerant version which is very similar to the Byzantine fault-tolerant version of the protocol. This version only considers crash faults and in turn it can tolerate up to a minority of node failures. The reason I started modeling was because I was suspicious how there was no need for using the epoch number knowledge in the protocol or the proof of safety in an asynchronous environment. The protocol employs only the longest chain rule. Longest chain does not necessarily mean the chain with the highest e...

In this 2020 technical report , the authors claim to present a very simple BFT consensus protocol. I am taking it that "textbook" in the title is used as praise for simplicity of the algorithm.  Nakamoto consensus is definitely simpler than Streamlet, but in contrast to Nakamoto consensus Streamlet provides deterministic finalization and does not suffer from the costly proof-of-work (POW) and the low-throughput POW induces. And, among the protocols that provide deterministic finalization, including PBFT, Tendermint, HotStuff, yes, Streamlet is the simplest protocol. So, yes, Streamlet deserves your attention. Streamlet protocol Streamlet is an amalgamation of existing techniques. It borrows stuff from Casper, HotStuff, and Elaine Shi's earlier work. But that's OK. The goal is to show the simplest protocol, not necessarily the most novel or the most efficient protocol. Here is the protocol, verbatim from the introduction of the paper. In Streamlet, each epoch has a de...

Masters of Doom is a 2003 book by David Kushner about John Carmack and John Romero cofounded id Software and produced video-games, including Doom and Quake.   The book was read by Will Wheaton. I  retrospectively recognized his voice from the "Ready Player One" book . He has a very enjoyable and engaging reading style, very close to voice acting. This was an OK book. It is engaging and worth a read if you don't know much about Carmack and Romero and early days of PC video gaming scene. Unfortunately the book lacks depth, and remains superficial in its analysis and observations. The characters covered, although interesting, come across always as one dimensional.   One thing that stands out in the book is John Carmack 's legendary focusing capability. Carmack is a learning machine. He can take off a couple weeks to master a new sub-area. In the book, he was quoted as saying that he likes the process [of learning and developing games], not just the end result. He took p...

Nice papers: Serverless in the Wild: Characterizing and Optimizing the Serverless Workload at a Large Cloud Provider Starling: A Scalable Query Engine on Cloud Function Services Lambada: Interactive Data Analytics on Cold Data using Serverless Cloud Infrastructure LogPlayer: Fault-tolerant Exactly-once Delivery using gRPC Asynchronous Streaming Automated reasoning for cloud computing systems Distributed systems class from MIT Interesting posts: Programming language design and compilers: where to start? NYT Is Threatening My Safety By Revealing My Real Name, So I Am Deleting The Blog Copy editing Creating a positive lab culture from Margo Seltzer Saccadic masking Podcast suggestions:  Revisionist History by Malcolm Gladwell Against the Rules by Michael Lewis Pet peeves: Lack of participatory and effective leadership across all levels and domains is disconcerting. Rough waters are truer tests of leadership. In calm water, every ship has a good captain. The immense popularity of ML ma...

The full title of the book is Enlightenment Now: The Case for Reason, Science, Humanism, and Progress . It came out in 2019, and Bill Gates called this book his "new favorite book of all time." For me, it is an OK book, I give it a 3.5 stars out of 5.  The book makes an important point about the importance of science and reason, and how much we accomplished thanks to them. As Yuval Harari nicely summarized, the book "extols the amazing achievements of modernity, and demonstrates that humankind has never been so peaceful, healthy, and prosperous." Ok, so it is a feel-good book, nothing wrong with that, right? Well, it is a very long-winded book, and it is hard not to get bored after some time. I really liked the first 50 pages: "Ok, this is going good, we have a good rapport as writer and reader". After page 100, I was like "OK dude I really get it, let's move on to something new now", and after page 150, I was pleading "Stop, stop, this ...

This paper appeared in OSDI 18, and is authored by Joshua Lockerman, Jose M. Faleiro, Juno Kim, Soham Sankaran, Daniel J. Abadi, James Aspnes, Siddhartha Sen, Mahesh Balakrishnan. The paper does not suggest many novel ideas or algorithms, but rather shows a nice amalgamation of existing ideas and algorithms for providing a more scalable version of a shared log across multiple datacenters. Having a shared log, and funneling all updates through a globally shared log  provides simplicity for building fault-tolerant consistent distributed systems. Tango paper from SOSP'13 , upon which they build here, argued for the simplicity benefits of such a system. Recently Jay Kreps wrote a nice and accessible explanation of the benefits of using globally shared logs for building distributed systems. Despite the simplicity it provides, maintaining a shared log with a system-wide total order is impractical, because it is expensive : At large scale, the single sequencer will be a bottleneck for the...

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