Matt Chung's Site

Category: Thinking out loud

  • Why is Lamport’s Scalar Clock only consistent, not strongly consistent?

    Why is Lamport’s Scalar Clock only consistent, not strongly consistent?

    For the last couple days, I’ve been watching the distributed systems video lectures and reading the recommended papers that cover logical clocks. Even after making multiple passes on the material, the concepts just haven’t clicked: I cannot wrap my mind around why Lamport’s clocks satisfy only consistency — not strong consistency. But now I think I have a handle on it after sketching a few of my own process diagrams (below).

    Before jumping into the examples, let’s first define strong consistency. We can categorize a system as strongly consistent if and only if, we can compare any two related event’s timestamps — and only the timestamps — and conclude that the two events are causally related. In other words, can we say “event A caused event B” just by inspecting their timestamps. In short, the timestamps must carry enough information to determine causality.

    Example: Time Diagram of Distributed Execution

    In my example below, I’ve limited the diagram to two process: P1 and P2.

    P1 executes three of its own events (i.e. event 1, event 2, event 3) and receives an event (i.e. event 4) from P2. P2 executes 2 events (i.e. event 1, event 2), sends a message (i.e. event 3) to P1, then P4 executes a fourth and final event. To show the sending of a message, I’ve drawn an error connecting the two events, (P2, 3) to (P1, 4).

    Logical clocks with an arrow from P2 to P1, showing causality between events (P2, 3) and (P1, 4)

     

    Cool. This diagram makes sense. It’s obvious from the arrow that (P2, 3) caused (P1, 4). But for the purposes of understanding why Lamport’s clocks are not strongly consistently, let’s remove the arrow from the diagram and see if we can reach the same conclusion of causality by inspecting only the timestamps.

    Removing arrow that connects (P2, 3) to (P1, 4)

     

    Next, let’s turn our attention to the timestamps themselves.

    Can we in any way say that (P2, 3) caused (P4, 4)?

     

    Just by comparing only the timestamps, what can we determine?

    We can say that the event with the lower timestamp happened before the event with the higher timestamp. But that’s it: we cannot make any guarantees that event 3 caused event 4. So the timestamps in themselves do not carry sufficient information to determine causality.

    If Lamport’s scalar clocks do not determine causality, what can we use instead? Vector clocks! I’ll cover these types of clocks in a separate, future blog post.

  • Failure: I want more of it.

    Failure: I want more of it.

    Students in the Georgia Tech program collaborate with one another — and collaborate with professors and teacher assistants — through a platform called Piazza. But at the end of the semester, this forum shuts off to read only mode, meaning we all lose connection with one another.

    Because of this, I recently created an e-mail list called computing-systems@omscs-social.com for other Georgia Tech Students who are interested in staying in touch. The motivation behind the mailing list is to share job opportunities, connect with other working professionals, and perhaps most important: provide peer support for one another. This felt like a natural next step since the study sessions (called “war rooms”) that I hosted were pretty successful.

    Piazza post. 70 views. 1 sign up

    But after posting a link on Piazza and sharing the idea, only 1 out of 70 people signed up. Total failure, right?

    Sort of.

    The lack of people signing up for the mailing list reaffirms two of my believes. First, the entire notion of “build it and they will come” is not true. Especially as software developers, we know that we can build the most shiny, most magical, most performant piece of software … and nobody can care.

    The second belief is that failures are a good thing. According to the late Randy Pausch, these setbacks are what we likes to call brick walls:

    The brick walls are there for a reason. The brick walls are not there to keep us out. The brick walls are there to give us a chance to show how badly we want something. Because the brick walls are there to stop the people who don’t want it badly enough. They’re there to stop the other people.

    – Randy Pausch

    In order to grow, you need to fail — a lot — because there’s no linear path to success.

    You can see this pattern of trial and error with Josh Pigard’s most recent venture that he recently sold for $4 million: big success, right? Yes, definitely.

    But notice all his other failed projects listed on his personal website.

    Josh Pigard – projects that were shut down

    On some level, the above are considered failures since the projects ultimately shut down. But that’s not how I see it. I’d like to think that Josh learned a lot of things from those failures, which fed and led him to building and selling his company.

    From this example alone, I think I can take away a lot of lessons learned. In particular, like my wife,  I am a perfectionist. I want — sometimes need — things to be perfect. But that’s surface level, only what maybe the outside can see. There’s a shadow side.

    Really, like many others, I have imposter syndrome. I’m constantly worried that I’m going to get exposed as some sham. My response to imposter syndrome? Striving to be right all the time. And I believe that taken too far, trying to be right all the time can stunt growth because to grow — personally and professionally — I need to constantly be experimenting, tinkering, trying out things that might just fail.

    To wrap things up: will I shut down and abandon the mailing list? Maybe. Maybe not.

     

  • 20s for education, 30s for experience, 40s for career.

    20s for education, 30s for experience, 40s for career.

    In my mid twenties, I was blessed to receive some of the best career, and quite frankly, life advice. During that period of my life, I was working as a director of technology, leading a small group of engineers. But I was getting ready to throw in the towel. I lacked both the experience and confidence needed. So I reached out to my friend Brian, asking him if he knew anyone who could help me with “executive coaching”. Thankfully, Brian connected me with a C level executive: let’s call him Phil (that’s actually his name).

    Prod, provoke, encourage

    When I met Phil at the Jerry’s Deli located in the valley, one of the first things he flat out told me was that executive coaching is bullshit. Despite that belief, he essentially coached me and gave me some sage advice that now I get to pass on.

    Seth Godin once stated that “About six times in my life, I have met somebody, who, in the moment, prodded me, provoked me, encouraged me, and something came out on the other side”.

    Phil is one of those 6 people in my life.

    The best career and life advice

    The sage advice is simple and sounds similar to Nic Haralambous’s advice “Plan in decades. Think in years. Work in months. Live in days”. But Phil’s advice offers a different perspective, another angle:

    20s for education. 30s for experience. 40s for career

    This advice stuck with me and helps me (re) calibrate my goals and values. Of course, life takes its own twists and turns. But as the Dwight Eisenhower said “Plans are worthless, but planning is everything”

    What does that look like in practice?

    20s for education is NOT synonymous with school. It really means soaking up as much as possible. This learning might take place in school but not exclusively. Because learning can happen anywhere and everywhere.

    Fail and fail a lot.

    For us tech folks, this might be learning a new programming language, dissecting the ins and outs of your compiler, picking up marketing or public speaking skills.

    The list goes on and on.

    30s for experience. This is where the rubber meets the road. Where theory and practice intersect. This may mean you want to switch roles (like how I switched from being a systems engineer to a software developer) or switch companies so that you can apply all that hard earned knowledge that you acquired in your twenties.

    Finally, 30s will feed into your 40s, where you get to establish your career. Maybe working for a small company, where you get to wear a bunch of hats. Maybe for a large corporation, where you hone in or specialize in a particular niche. Or maybe as an entrepreneur, building your own product or service.

    Now what?

    I’m actually revisiting these words of wisdom. Right now. For the last six months or so, I’ve been overly focused on an upcoming promotion from a mid to senior level engineer at Amazon. Instead of chasing this new title — cause that’s all it really is — I’d rather redirect my focus and make mistakes, stretch myself and find opportunities that put me in a uncomfortable (but growth inducing) experiences.

  • Being paged out of bed at 3 AM …

    Being paged out of bed at 3 AM …

    Sadly I didn’t get to start the day off with writing, my morning routine, since my phone paged me out of bed at 3 AM due to an operational issue from work that lasted about about three hours. Because of this, I know that I’ll feel “off” the rest of the day given that I’ve been awake for over 5 hours and the time is barely 9 AM. Oh well. Time to heat up another Chai Latte to keep me awake for the day …

    Sometimes I wonder if this is all worth it …

  • Farmhouse style doors – sliding door ideas for my home office

    Below are a couple photos of farm house doors that I think have good taste. I’m thinking of adding one of these type of doors to my new home office and wanted to share a couple of styles that I thought were both warm and aesthetically pleasing, two qualities I’m aiming to bring out of this new set up of mine.

    Grey farm house door. Credit: jettsetfarmhouse.com

     

    Beautiful brown grey farmhouse door. Credit – https://www.instagram.com/sheltercustombuiltliving/
  • What’s the point of the parity flag in the dissemination barrier?

    What’s the point of the parity flag in the dissemination barrier?

    I’m implementating the dissemination barrier (above) in C for my advanced OS course and I’m not quite sure I understand the pseudo code itself. In particular, I don’t get the point of the parity flag …. what’s the point of it? What problem does it solve? Isn’t the localsense variable sufficient to detect whether or not the threads (or processes) synchronized? I’m guessing that the parity flag helps with multiple invocations of the barrier but that’s just a hunch.

  • Learning how to build a personal brand (two books I picked up)

    Learning how to build a personal brand (two books I picked up)

    I want to learn how to better market myself and what it means to create my own personal brand and how I might be able to apply these marketing skills in my career (as a software developer and computer scientist) and as a writer. Because I do wonder what sort of impact and influence I would have if I applied even an ounce of marketing or branding.

    I’m planning on sinking my teeth into two different marketing books. My guitar instructor had recommended Seth Godin’s This is Marketing and a hacker news user recommended an e-book titled Authority by (someone I’ve never heard of) named Nathan Barry. I’ll take a crack at these two books and report back on the main takeaways and whether or not I recommend you reading them.

    At this moment in time, I have no clue what it means to build a personal brand (in all honestly I don’t even know what a personal brand means). Nonetheless, I do think learning about a little marketing and branding (really what’s the difference between the two) will be a worthwhile, non-technical skill to develop since I’d like down the line to become a full time writer and teacher and think marketing and branding will play a key role in making that happen.

  • Making sense of the “sense reversing barrier” (synchronization)

    Making sense of the “sense reversing barrier” (synchronization)

    What’s the deal with a sense reversing barrier? Even after watching the lectures on the topic, I was still confused as to how a single flag could toggle between two values (true and false) can communicate whether or not all processes (or threads) are running in the same critical section. This concept completely baffled me.

    Trying to make sense of it all, I did some “research” (aka google search) and landed on a great article titled Implementing Barriers1.  The article contains source code written in C that helped demystify the topic.

    Sense Reversal Barrier. Credit: (Nkindberg 2013)

     

    The article explains how each process must maintain its own local sense variable and compare that variable against a shared flag. That was the key, the fact that each process maintains its own local variable, separate from the shared flag. That means, each time a process enters a barrier, the local sense toggles, switching from 1 to 0 (or from 0 to 1), depending on the variable’s last value. If the local sense variable and the shared flag differ, then the process (or thread) must wait before proceeding beyond the current barrier.

    For example, let’s say process 0 initializes its local sense variable of 0. The process enters the barrier, flipping the local sense from 0 to 1. Once the process reaches the end of the critical section, the process compares the shared flag (also initialized to 0) with its local sense variable and since the two do not equal to one another, then that process waits until all other processes complete.

    References

    1. Nkindberg, Laine. 2013. “Implementing Barriers.” Retrieved September 17, 2020 (http://15418.courses.cs.cmu.edu/spring2013/article/43).
  • Thinking out loud – Not fully understanding virtually indexed physically tagged (VIPT) details

    Thinking out loud – Not fully understanding virtually indexed physically tagged (VIPT) details

    I’m really struggling to intimately understanding virtually index privately tagged concept. From a high level, I get that VIPT is an optimization technique, parallelizing both the translation of virtual addresses to physical and the cache look up of the physical address.  This seems impossible at first since the cache depends on the physical frame number (PFN).

    So in order to accomplish this, we’ll use the some bits of the VPN to search in the TLB and then the least significant bits when searching the cache. This makes sense. But what I don’t quite fully don’t understand is why we have to limit the size of the cache in order to avoid aliasing (i.e. different virtual addresses that end up mapping to the same physical frame).

    Thinking out loud here … I suppose that if the index of the physical bits bleed into the virtual address, then we actually do not avoid the aliasing problem, the issue of having more than one virtual address map to the same physical frame.

    Ok, I think I got it.

    But what’s the catch?

    You only can have a very small cache, the size equal to the page size multiplied by the set associativity. This means that the only way to increase the size of the cache is by increasing the associativity which ultimately increases the look up time as well since the cache has to look the tag up across multiple cache lines.

    Reference

    1. https://cs.stackexchange.com/questions/68492/does-the-aliasing-problem-show-up-in-a-virtually-indexed-physically-tagged-cache
    2. https://cseweb.ucsd.edu/classes/fa10/cse240a/pdf/08/CSE240A-MBT-L18-VirtualMemory.ppt.pdf