Metadata

This is a lovely paper (2016) from Marcos Aguilera and Doug Terry . It is an easy read. It manages to be technical and enlightening without involving analysis, derivation, or formulas. The paper talks about consistency. In distributed/networked systems (which includes pretty much any practical computer system today), data sharing and replication brings up a fundamental question:  What should happen if a client modifies some data items and simultaneously, or within a short time, another client reads or modifies the same items, possibly at a different replica? The answer depends on the context/application. Sometimes eventual consistency is what is desired (e.g., DNS), and sometimes you need strong consistency (e.g., reservations, accounting). The paper points out two different types of consistency, state consistency  and operation consistency , and focuses mainly on comparing/contrasting these two approaches. When I see the terms state versus operation consistency, witho...

I started my sabbatical work with t he Microsoft Azure Cosmos DB team recently. I have been in talks and collaboration with the Cosmos DB people, and specifically with Dharma Shukla, for over 3 years. I have been very impressed with what they were doing and decided that this would be the best place to spend my sabbatical year . The travel and settling down took time. I will write about those later. I will also write about my impressions of the greater Seattle area as I discover more about it. This was a big change for me after having stayed in Buffalo for 13 years. I love the scenery: everywhere I look I see a gorgeous lake or hill/mountain scene. And, oh my God, there are blackberries everywhere! It looks like the Himalayan blackberries is the invasive species here , but I can't complain. As I go on an evening stroll with my family, we snack on blackberries growing along the sidewalk. It seems like we are the only ones doing so ---people in US are not much used to eating fruit...

This article by Leslie Lamport has appeared recently at the Distributed Computing & Education Column. This article focuses more on the distinction between the TLA+ modeling language versus programming languages. Earlier I had written a blog post about more general benefits of modeling and model-checking. This is not a technical article so instead of trying to summarize/review the main points, I just include some choice quotes from the article below. The most important takeout message is at the end, which I emphasize with the bold font. Algorithms are not programs, and they can be expressed in a simpler and more expressive language. That language is the one used by almost every branch of science and engineering to precisely describe and reason about the objects they study: the language of mathematics. Programming is too often taken to mean coding, and the algorithm is almost always developed along with the code. To understand why this is bad, imagine trying to discover Eucli...

Today I mused a bit on a futuristic research outlook for blockchain/decentralized consensus. Here is what occurred to me: a merger of blockchain consensus with ubiquitous/spatial computing. Partially-replicated decentralized consensus Here is the first piece of the puzzle. A drawback with current blockchain/decentralized consensus work is that they require full-state-replication (of the entire chain or DAG) at each participating node. This is a big scalability bottleneck. Replication should be on a need to know basis. What is the point of replicating transactions/state that is relevant for Buffalo, NY to nodes in Delhi, India. Assume we fix that. ( That will involve a good amount of research on graph algorithms.) And we use lightweight energy-efficient decentralized consensus algorithms, such as Avalanche, so that these can work on lightweight portable renewable power devices. Now on to the next piece of the puzzle. Ubiquitous/spatial computing Think about next genera...

impact (n) 1. the action of one object coming forcibly into contact with another 2. the effect or influence of one person, thing, or action, on another Impact (with the second meaning :-) is an often talked about desirable thing in academic and research world. Impact is especially important for promoting an associate professor to a full professor status. Unfortunately there is no well-defined description or an objective way to quantify impact. There are approximated metrics, each with significant flaws: Citation count is easily quantifiable --Google Scholar shows your citation count and h-index. However, this can be tricked. Some journals have boosted their impact factors by asking accepted articles to cite other articles from the journal. Publishing in popular/crowded areas (e.g., wireless networks) can also boost citation count. It is possible to have high citation count with little impact, and little citation count with high impact. As a personal anectode, many of the work I...

This is a half-baked exploratory piece about how some self-stabilization ideas may relate with blockchain consensus in open/permissionless environments. I will write about some similarities and some major differences between the self-stabilizing distributed algorithms work and blockchain consensus deployments. Self-stabilization Let's start with a brief review self-stabilization . Stabilization is a type of fault-tolerance that handles faults in a principled unified manner instead of on a case-by-case basis. Instead of trying to figure out how much faults can disrupt the system's operation, stabilization assumes arbitrary state corruption, which covers all possible worst-case collusions of faults and program actions. Stabilization then advocates designing recovery actions that takes the program back to invariant states starting from any arbitrary state. This makes stabilization suitable for dealing with unanticipated faults. The most distinct property of self-stabilizat...

I didn't know what to expect when I picked this book from the library. A book by an astronaut could turn out to be boring and mundane for me. The thing is, I am interested in space, but I wouldn't say I am passionate about it. I never wished I could be an astronaut as a child (or as an adult). I guess I wanted to be the engineer that designed those systems, rather than the astronaut that piloted them. Long story short, I enjoyed reading this book a lot. I never got bored, on the contrary I was very engaged. The book interleaved Scott Kelly 's growing up and his 1 year stay at the International Space Station (ISS) at every other chapter. At the end of the book, Scott's life timeline has caught up to the beginning of his year-long ISS stay, and his ISS stay timeline concluded with the Soyuz return capsule entering the atmosphere. I learned a lot about the space program. It still weirds me out that while we are very much earth-bound with our lives, technology, perspect...

This paper is by Team-Rocket ---the authors are pseudonymous, I presume a guy, a gal, and a cat is involved. I learned about the paper when Emin Gun Sirer announced it on Twitter. Here is the synopsis from the paper. "This paper introduces a brand new family of consensus protocols suitable for cryptocurrencies, based on randomized sampling and metastable decision. The protocols provide a strong probabilistic safety guarantee, and a guarantee of liveness for correct clients." Below I first summarize the protocols and at the end I will provide my comments/evaluations. The analysis of the paper is very strong and span 8 pages, but I skip that section in my review. Introduction Traditional consensus protocols incur high communication overhead and accurate knowledge of membership. So while they work great for less than 20 participants, they do not work for large numbers of participants and open/permissionless environments. Nakamoto consensus family protocols address tha...