Effective Papers

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

It seems like 20th century was the golden age of science and technology . Just look at that list, so many breakthroughs in math, physics, astronomy, biology, medicine, energy, electronics, computing . Some of these include: set theory, topology, abstract algebra, formal logic, incompleteness theorems, theory of computation special relativity, general relativity, quantum mechanics, fundamental interactions, electroweak interaction, nuclear fusion Big Bang theory, space probes, moon landing, space station, hubble space telescope DNA structure, human genome project, antibiotics, many vaccines, many drugs Transistor, semiconductor, integrated circuits, MOS image sensors, CPUs, radio, TV, Internet What about the breakthroughs in the last 30 years, 1990 onwards? There isn't any significant breakthroughs we can point to in basic sciences except for detection of gravitational waves and Higgs boson . On the applied side of things we have the human genome project and personal computing rev...

This is a 14 page booklet by David Isaacs Eric E. Vogt, Juanita Brown, available online at https://umanitoba.ca/admin/human_resources/change/media/the-art-of-powerful-questions.pdf I am fond of questioning. My 2018 resolution was to add MAD questions to each blog post. I also wrote about how to ask better questions a couple of times in this blog. + Master your questioning skills + How to ask better questions This booklet is a pretty nice addition to my collection. Below I include my highlights, with my italicized commentary in-lined. Speaking of questions and collections, you should definitely check this comic.  Highlights from the book  The usefulness of the knowledge we acquire and the effectiveness of the actions we take depend on the quality of the questions we ask . Questions open the door to dialogue and discovery. They are an invitation to creativity and breakthrough thinking. “If I had an hour to solve a problem and my life depended on the solution, I would spend the ...

A week or so ago, I told you I wanted to brainstorm about the future of work . Well, here it is for what it is worth. Work wants to be free/liberated  As liberties progress and more welfare is created, our expectations move higher up in Moslow's hierarchy . We are not satisfied with achieving bare survival by means of our work, and we want to thrive, flourish, and express ourselves via our work. We long to have more autonomy and freedom of choice and expression in our work. We like to pursue our own enterprises as part of our work. We already see things moving away from the traditional industrial model with company loyalty, closer to this type of model. In software field, which is well off compared to others, people switch jobs frequently, and try to build their own brands/niches, and demand fulfillment from their work. As these trends shape the future of work, we will see a growing gig economy that is served/supported by algorithmic platforms. Some primitive examples of this is us...

Future of work is a very interesting topic. This is something I would like to think about and brainstorm. But since the topic is very broad, the attempts to talk about future of work can get hazy and vague.  NSF has released this call for proposals on Future of Work.  It invites researchers to start addressing the needs/problems/challenges future work with a "convergent perspective". I am accustomed to seeing vague and extravagant language in NSF calls, but I think this one surpassed the usual. The word convergent/convergence appears 22 times in the call. (I think convergent is a new word for interdisciplinary in this context.) I guess a similar thing happened with the Microsoft Faculty Summit 2019. Last July, I was at Microsoft for my sabbatical, and had a chance to attend the Microsoft Faculty Summit, whose subject was "Future of Work" . It was a two day workshop, and I was very motivated to learn as much as I could from the workshop, because the topic is very int...

This is the last book in Liu Cixin's Remembrance of Earth's Past trilogy. I had written reviews for the Three Body Problem and Dark Forest before . So for completeness sake, I write my impressions about this book as well. This time I try not to talk much about the plot, and try to keep this spoiler-free. This book is epic, in terms of the space distance and timeline it covers. It is awe-inspiring in that vastness in space and time sense, and makes you think at the universal scale. This book feels much more hardcore sci-fi than the previous two books, and less believable than them. The book also feels rushed in character/plot development (definitely not length) compared to the previous two books. But all in all, it is a very captivating science fiction and I couldn't stop thinking about it even one week after finishing the book. The book still has a very cynical and very pessimistic view of human nature (as well as alien nature). The universe is a dark forest, where everyon...

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

Companies care about cheap computing. Well, the first thing they care about is usability: Is it easy for average programmers to develop solutions using the framework? And the second thing they care about is cheap computing: Does this break the bank? Can I do this cheaper? Speed, efficiency, elegance, technical strength... These are often not of interest. People are OK with their analytic jobs return results hours later. We watched aghast, at the beginning of Hadoop epidemic, people use MapReduce for doing analytics in a wasteful and slow manner. I was recently thinking about this question: How can we trade-off speed with monetary cost of computing?  If the constraints are that the user will not need the results before a couple hours but it would be nice to get the results in a day, what is the cheapest way to get this analytics job done in the cloud? While distributed systems may be the answer for a lot of questions (such as providing fault-tolerance, low-latency access for geo-dis...

Consider the atomic storage problem , which is a simpler problem than consensus. CAP theorem says that when there is a partition, you will need to sacrifice strong-consistency or high-availability. Using leases, it is possible to sacrifice availability for sometime (until lease expires), and reconfigure the storage system (often by shrinking the quorum) to keep providing availability. Consistency is preserved throughout, and availability is sacrificed only during lease expiration time. This is a good tradeoff. (I am going to bring up the question of whether this may help circumvent CAP at the end of the post.) But is this power unique to leases? Is there a way to explain this in an alternate way using only failure detectors instead of leases? This is the question I want to explore here. Many distributed systems implement leases with just countdown timers and without NTP timestamps. This is because in the short-term the rate of clocks at processes don't drift too much. So maybe, we ...