Jess and I received our first dose of the Pfizer vaccination, our second dose scheduled for 3 weeks from now.
We were able to get the vaccination since Jess had heard, through a mom’s group she’s part of, that breastfeeding mothers (along with their partners) were eligible through a Kaiser clinic. So after signing up a week early, we strolled into the Renton vaccine clinic and were in and out within 20 minutes.
What are the after effects?
Jess is a super human and had almost zero effects (she did dose herself lots of vitamin C a week before, so that could be the reason)
I felt mentally foggy within the first hour and by the second hour, I was very lethargic, my energy zapped, requiring me to take a 2.5 hour nap to recover
Before heading to bed, I had a dead arm, my arm feeling as though someone punched me about 100 times
Getting the vaccination wasn’t a black/white decision
The vaccination is not FDA approved
The vaccination was made publicly available at an accelerated rate
Jess is/was worried about the long term impact
For me, the vaccination is one step forward in returning back to a sense of normalcy, reducing my anxiety and general nervousness of feeling that I’m going to catch COVID-19
We can more safely travel to U.K. and visit Jess’s family
In the paper “PAXOS made moderately complex”, the authors introduce unfamiliar concepts not mentioned in the original PAXOS paper, concepts such as slots, slot in, slot out, and WINDOW. I found these concepts difficult to understand despite reading both the accompanying pseudo code as well as their Python implementation.
This post aims to shed light on these concepts and better understand how the following invariant holds:
R5: A replica proposes commands only for slots for which it knows the configuration: slot_in < slot_out + WINDOW
The rest of the post focuses on the replica only. We will not discuss the actual consensus algorithm, also known as the SYNOD; this topic will be covered in a separ
SLOTS Overview
Slots are to be occupied by decisions
SLOT_IN points to the next “free” unoccupied slot
SLOT_OUT points to the next decision to be executed
SLOT_IN advances by 1 with every new decision received by leaders
SLOT_OUT advances by 1 with every execution of a decision by the replica
SLOT_IN + WINDOW is N number of slots allowed to be buffered
SLOT_OUT trails behind the SLOT_IN as more decisions flow into the replica
SLOT_OUT == SLOT_IN means replica has processed all it’s commands
Figure 1 – Imagine a WINDOW=5. Initially, both slot_in and slot_out both point to slot 1
Then, the replica, as it receives requests from clients, will send proposals to the leaders. The leaders will, as part of its consensus algorithm, will respond with decisions commands, each accept command tied to a particular slot position. We won’t discuss the consensus algorithm as part of this post (but perhaps another).
Figure 2 – Replica sending a proposal for slot 1
Then, as the replica receives decisions, it will fill the slot accordingly. Every time a slot fills, the slot in pointer advances by one.
Figure 3 – As replica receives decisions, it inserts into its buffer, advancing slot in by 1
Next is the perform phase. The replica will execute the decision — it’s associated command — and will advance the slot out index by 1.
After receiving a decision, the replica will fill in the slot associated with that particular decision.
Figure 4 – Replica receives decision and fill in the particular slot associated with the decision
Then, for illustrative purposes, imagine that the replica sends out another proposal (not shown in the figure below), advances the slot in by 1, then fills in the second slot.
Figure 5 – Slot IN points to index 3 and Slot OUT still pointing to slot 1
Finally, during the perform phase, the replica will advance the slot out pointer.
Figure 6 – As the replica executes commands in the slot, the slot OUT index advances. The slot, previously yellow, is now green, symbolizing that the occupying command has been executed
Finally, in this example, the replica executes the next command, advancing SLOT OUT which now points to the same (unoccupied) slot as SLOT IN.
Figure 7 – Replica executes it second outstanding decision, advancing SLOT OUT by 1, which now points to the same (unoccupied) slot as SLOT IN
I’m now half way through Distributed Computing course at Georgia Tech and us students are now tackling the penultimate project: building a replicated state machine using PAXOS. This project will be challenging (probably going to require 40+ hours) and it’ll put my theoretical knowledge to the test and reflect back, in a couple weeks, how much I learned.
Presently, here’s my little understanding of the consensus algorithm:
Current PAXOS understanding
Servers play different roles – Proposer, Acceptor, Learner
Proposers send proposals that monotonically increase
Proposals are accepted if and only if a majority of the quorum accept them
The 2PC (2 phased commit) protocol essentially tells us whether or not a particular transaction is committed or aborted
Guaranteeing linearzability means that, from the clients perspective, real time (i.e. wall clock) should be respected and the client should view the system as if there is a single replica
Future PAXOS understanding
How exactly PAXOS guarantees consensus via its 2 phased commit protocol
How does a server determine its role (or does it play multiple roles)
How to handle the edge cases (say two proposals arrive at the same time)
What role does a client play? Does it serve as a proposer?
How does leader election work in PAXOS?
Should I just try and mimic the Python based code described in Paxos made moderately difficult
How will replication work as the number of nodes in the system scales (say from 3 to 5 to 10)
How to detect (and perhaps avoid) split brain (i.e. multiple leaders)
References
Majority quorum can be defined as floor(n/2) + 1
Python implementation described https://www.cs.cornell.edu/courses/cs7412/2011sp/paxos.pdf
I’m preparing for my Distributing Systems midterm and I was struggling to understand the differences between serializability and linearizability (why are these two words so difficult to spell right). Apparently, these two concepts are very different. To gain some clarity, I searched online and found this awesome YouTube video posted by Martin Kleppmann ; in the video, he dives deep into linearizability and I wanted to share some of the key take aways
Key Takeaways
Happens before relationship (coined by Leslie Lamport) deals with causality and only applies to message sends and receives, related to logical clocks.
Linearizability focuses with not with logical clocks, but with real time
Linearzability states that an operation must take place sometime after it started but before it ended. That’s not entirely clear, so let’s let’s imagine a scenario with two clients: client 1 and client 2. Client 1 performs a write key=x value=0. And imagine client 2 performs a get key=x. And finally, suppose that the key value store current contains a key=x, value=100. With linearzability, it’s entirely possible that if both client 1 and client 2 overlap, that client 2 gets either value=0 or value=100.
Linearzability is not serializability. They are not the same. The latter is isolation between transactions; as if they are executed in some serial order. The former is multiple replicas behaving as if there is a single replica.
Ever since I was little boy, if any of my friends were bullied or picked on, and I noticed they couldn’t defend themselves, I would speak up on their behalf. Speaking up for others has always come naturally for me and it’s habit that I still flex even as an adult. However, these days, I’m a tad more reluctant to take action; I’ve learned that sometimes its best to allow people the opportunity to fight their own battles. Knowing when to stay silent or speak up for others is not so black and white: it’s an art.
I’m constantly walking a fine line.
In fact, this blog post was sparked by another student in my OMSCS program, who posted a question on the online forum, which lead to a discussion I wasn’t sure I should engage. This particular student had asked for a one day extension for the first programming project, admitting that they vastly underestimated the complexity of the assignment. Then, another anonymous student chimed in, complaining that it would be “unfair” for the other students who actually “budgeted” their time. As soon as I read this anonymous person’s comment, I immediately felt annoyed and wanted to send a knee-jerk response but decided to step away from my keyboard since I didn’t want to type something I would regret.
Instead, here’s how I responded:
Piazza post – asking for a single day extension
And I’m glad I did respond. Because since voicing my opinion, a handful of other students started replying to the thread, taking a similar stance to mine.
In general, I’m motivated to speak up for others is because I fervently believe in the following quote:
“The only thing necessary for the triumph of evil is for good men to do nothing.”
In “Consistent Global States of Distributed Systems: Fundamental Concepts and Mechanisms”, the authors propose capturing a distributed system’s computation using a time series graph. Each row in the graph represents a process (e.g. P1, P2, P3), and each tick (e.g. e1, e2) within that row represent a an event: a local event, a send message event, a receive message event. For example, looking at the figure above, P1’s event is a local event but P1’s second event represents the reception of the message sent from P2.
Snapshot of distributed system using cuts
Now, say we wanted to take a snapshot in time of all the processes. How do we model the system’s state? Well, the authors describe a technique they call cuts. Essentially, a cut is a tuple, each element signifying each process’s last event (i.e. called a frontier) that should be considered part of the snapshot state.
Cuts of a distributed computation
In the figure above, two cuts exist. The first cut is (5, 2, 4), the second cut (3,2,6). For the first cut, we include P1’s events up to (and including) event 5. For the same cut, we include P2’s events up to (and including) event 2.
Consistent versus Inconsistent
Now, there are two types of cuts. Consistent and inconsistent cuts. Returning back to the figure above, the first cut (C) is considered “consistent” while the latter (C’) “inconsistent”.
Why?
A consistent, according to the authors, can be defined using mathematical notation.
Definition of consistent cut
If that’s not clear, they offer another explanation: “In other words, a consistent cut is left closed under the causal precedence relation.”
Inconsistent cut in layman terms
Okay, what does this really mean? I still find it a bit confusing, so let me try to form it in my own words.
If an event (event_x) within tuple was caused by another event (event_y), then the causal event (event_y) must be included within the tuple. As an example, take a look back at the figure above. P3’s event 6 was caused by P1’s event 5. However, the cut’s frontier event for process 1 is event 3, failing to include P1’s event 5. Therefore, this cut can be classified as inconsistent.
Like almost every other parent, my wife and I are doing our best to shelter our 16-month year old daughter, Elliott, in the midst of the COVID-19 pandemic, us parents trying to fabricate a bubble with some sense of normalcy. Up until recently, I tricked myself into believing that we could mask (or minimize) the impact of social distancing on Elliott. Unfortunately, I no longer hold on to that belief.
On Monday afternoons, Jess attends a (remote) hour long appointment and during that time, I break away from my office and watch over Elliott. This past Monday, Elliott and I walked — well, I mostly carried her — to the neighborhood park located right around the corner. And when we arrived, in the distance (about 50 feet) were two young girls (around six and two years old) and their nanny, the three of them sitting cross-legged in a circle on the ground, feasting on their homemade picnic.
Elliott waved her little hand at them and caught the attention of the one of the little girls, who raced over and introduced herself, abruptly stopping just about six feet away from us.
“I’ll keep my distance, because of the coronavirus.”
After shooting the shit with this 6 year old for a couple minutes, we parted ways and Elliott and I continued walking towards the swing area. I noticed that Elliott was still gazing at the two little girls sitting in the distance. When I planted Elliott down on her own two feet, she spun around and faced the direction of the girls, turned her heads towards me, then stretched her arm our towards them, pointing her index finger in their direction, signaling to me she wanted to go play. But I had to explain to her that she couldn’t and that we needed to keep our distance.
Elliot started bawling. Non stop.
I felt so sad for her.
I squatted down to her eye level, trying (as best as I could) to gently explain to her that she couldn’t go play with them. But it was no use. Nothing I said comforted Elliott.
God damn this pandemic.
I hope and pray that this pandemic ends soon and that we can return to our “new normal”, a normal that allows children to run around with each other, play tag, hug one another, without them fearing, or their parents fearing, for their lives.
Leslie Lamport, a world renounced computer scientist, first published the paper “Part-time parliament” back in 1990. Unfortunately, that paper well not well received, primarily due to the fact that the consensus protocol was described in the context of obscure ancient Paxos civilization. The paper was not was received among computer scientists and Leslie Lamport followed up by publishing another version of paper titled “Paxos made simple.”
Over the last couple days, I’ve been reading and carefully studying the paper, making (so far) three passes. From the title, you would think that the paper is written such that it could be easily understood by us computer scientists. It’s supposed to be simple, right?
Nope.
In fact, I’m finding it incredibly difficult to conceptualize the consensus protocol, unable to succinctly describe the protocol in my own words. The paper’s title misleads its readers!
Frustrated with my own inability to understand the paper, I set it aside and decided to pick up another (optional) reading assignment prescribed by my distributed systems course, the paper titled “In Search of an Understandable Consensus Algorithm.” After reading the first couple paragraphs, I feel a sense of relief because on the second page, the authors share both my frustration and confusion about PAXOS:
“The first drawback is that Paxos is exceptionally difficult to understand. The full explanation [15] is notoriously opaque; few people succeed in understanding it, and only with great effort. As a result, there have been several attempts to explain Paxos in simpler terms [16, 20, 21]. These explanations focus on the single-decree subset, yet they are still challenging. In an informal survey of attendees at NSDI 2012, we found few people who were comfortable with Paxos, even among seasoned researchers. We struggled with Paxos ourselves; we were not able to understand the complete protocol until after reading several simplified explanations and designing our own alternative protocol, a process that took almost a year”
After realizing that I’m not alone in failing to grok PAXOS, I started searching the internet for other resources that better describe PAXOS. I found a couple great write-ups as well as the “defacto” lecture describing PAXOS:
Apparently, this paper is a seminal piece of work that goes on to describe and prove that, given a single process failure within a distributed system, the underlying system cannot achieve consensus (i.e. the nodes cannot reach a state where they all agree on some proposed value). That’s right: not difficult, but impossible. Assuming that this theorem holds true, how the hell do we even build robust distributed systems that can tolerate failure? Surely there must be a way. Otherwise, how the hell do popular cloud services like Amazon S3 and Amazon DynamoDB guarantee high availability and consistency.
My gut tells me that the authors of the paper — Fischer, Lynch, Patterson — make strict assumptions about the underlying system. And if we can somehow relax these assumptions, then we can in fact build highly available distributed systems. But, I’ll find out soon since I’ll be reading both this paper as well as another seminal piece of work “Paxos made simple” by Leslie Lamport.
I recently watched a YouTube video titled “My Guitar Teacher TOMO FUJITA Gives Words of Wisdom”. In this video (below), YouTuber Mary Spender interviews Tomo Fujita, a guitar instructor who taught at Berkelee school of music for over 20 years; he takes his years of accumulated knowledge and shares some words of wisdom. From this interview, I took away three lessons: practice music that you are drawn to , identify 5 inspirational guitarists, and record and analyze yourself playing guitar.
Practice music that you are drawn to
Here’s the gist: stop trying to be someone you are not.
Many of us aspiring guitarists incorrectly believe that in order to be a “good” guitarist, we need to be able to play either classical, blues, or jazz — even if that’s the type of music we don’t listen to.
Tomo shared an example of one of his students who declared “I want to get good at Jazz” and his student proceeded to enumerate all the ways in which he would become a Jazz player, declaring that he’ll begin with learning all the Jazz music theory. Tomo Fujita responded, “What sort of Jazz do you listen to?”.
Radio silence.
The student admitted they don’t listen to any Jazz and Tomo shared his philosophy: that unless you practice the music that you love, you’ll never get good at it. At best, you’ll nail the mechanics. But ultimately, the playing with feel empty. He’s right.
So stop practicing music you don’t enjoy — right now — and just be your authentic self. Enjoy pop music? Play and write pop songs! You like getting down to reggae ? Drill Bob Marley songs! Also, don’t feel like you need to restrict yourself to one genre either. But once you’ve identified the types of music you want to pursue playing, then you should identify 5 guitarists who inspire you.
Identify top 5 guitarists who inspire you
Another useful exercise he mentioned was name 5 guitarists that inspired you. Not six. Not 10.
Then, once you identified the top 5 artists, research them. Learn their history and how they became the artist they are today. Identify their inspirations, recursively tracing inspirations to the root. This exercise helps inform and influence your own style.
Record yourself for feedback
If you never record yourself — using audio, video, or both — then it’s difficult to improve as a guitarist. You miss out on feedback, miss out on opportunities to discover your own habits and area sof improvement.
I recently started recording myself and publishing the videos to YouTube. I upload videos not to generate millions of views, but for multiple reasons. First, I’m documenting my progress, something I wished I did when I first picked up the guitar a couple years ago. Second, through recording and more importantly, watching and hearing myself allows me to analyze my playing, allowing to identify skills that need to be brushed up on. Finally, recording is a forcing function, pushing me to generate a large volume of work, the only real way, I think, to improve music craftsmanship.
