Our front yard needs work. About 3 weeks ago, I made my first attempt at overseeding and although a couple seeds germinated, the lawn was left with lots of bare spots.
Several bare spots in the lawn
So I’m taking a second stab. This time around though, I’m not just going to simply chuck seeds on top of the grass. Instead, I’m taking going to take the following steps:
As a new lawn enthusiast, I have no clue as to not whether this will work. It’s sort of an experiment. I’ve watched dozens of YouTube videos and it’s time for the rubber to meet the road. So I’ll be documenting the journey and will report back in a couple days as I continue to water the lawn. Regardless, I’m enjoying the unknown and I’m in good company:
Metric keeping me company while I work on the lawn
I just finished Spring 2021 at Georgia Tech OMSCS and published a farewell note on the classroom’s forum (i.e. Piazza platform) and would like to share that here:
This was one hell of a semester! Hats off to professor Ada and our great TAs — I learned a great deal about both theoretical and practical distributing computing knowledge, experiencing first hand how tweaking a retry timer by a few hundred milliseconds can make or break your day.
But above all else, thanks to all the other students in this class, I felt extremely supported, more supported than any of the 8 courses I had previously taken in the program.
More than once throughout the class I contemplated just throwing in the towel. The last couple projects in particular really wore me out mentally and emotionally (e.g. 10 hours troubleshooting for a one-line fix to pass one single test) and if it wasn’t for the constant support of all my peers over Piazza and Slack, I would’ve probably not only dropped from the course but the journey itself would’ve felt a lot more isolating, especially in the midst of the pandemic.
Now, there are definitely rough edges with this course, particularly around pacing on the last couple projects. But given that this was the first semester that distributed computing was offered as part of OMSCS, I anticipated minor bumps coming into this class and have no doubts that the logistics will get smoothed out over the next couple semesters.
Finally, for those of you graduating this semester, congratulations! Way to go out with a bang. And for the rest of us, see you next semester!
Thanks again for all the support and let’s stay connected (contact info below). Now, time for a much needed nap after taking the final exam:
After watching dozens of YouTube videos on lawn care, I decided about two weeks ago to overseed the front lawn and water the grass twice a day (I really used to think that the earth would just magically nourish our yard). And up until this morning, I wasn’t entirely sure if all my effort was wasted, since it’s really difficult to spot whether or not seeds were actually germinating. On top of this daily maintenance, I’ve been also singing to them, giving them some verbal love.
My first lawn seeds germinating 1.5 weeks later
And this morning, about 1.5 weeks later after initial seeding, I discovered that my little seeds were starting to germinate! Proof! Finally! I was so ecstatic that I snapped a couple photos and then bolted inside, sharing the photos with Elliott and Jess.
I suppose this is one of the silver linings of COVID-19 and being locked down at home for the last year? I’m turning into a lawn care nut.
The above diagram I diagrammed illustrates the impact to a network packet when setting the maximum segment size in iperf3. With an MSS of 1436, the segment (i.e. TCP payload) ends up 1424, due to the overhead of the 12 byte TCP options.
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.
