CSE138 (Distributed Systems) L4: vector clocks, FIFO/causal/totally-ordered delivery
ฝัง
- เผยแพร่เมื่อ 10 ก.พ. 2025
- UC Santa Cruz CSE138 (Distributed Systems) Lecture 4: Lamport clocks recap; vector clocks (continued); delivery vs. receiving; properties of executions: FIFO delivery, causal delivery, totally-ordered delivery; implementing FIFO delivery
Recorded April 8, 2021
Professor Lindsey Kuper users.soe.ucsc...
Course website: decomposition.a...
Schedule of topics: decomposition.a...
These videos single handidly saving me in midterm season.
Thanks Prof. Maybe I did not pay enough attention to my lecture but your explanation with hand drawn graph is just clearer and better!
This video saved my life before distributed system midterm exam. Tons of Thanks.
Found this video series after reading DDIA(Martin Klepman book). This has been so helpful to understand the concepts introduced in DDIA. Thanks a ton!!
Thanks for watching.
@@lindseykuperwithasharpie Yep, I took a course on Advanced Operating Systems that covered ur DS course, even though I finished the course understood all the concepts it didn't help me to find real world problems, then I read DDIA where in specifically it talked about problems of leader based replication and message causality was one of the drawback. Everything I learned from ur DS and my AOS course was aligned when I read that chapter and watched ur videos. I recommend everyone to follow DDIA and ur DS course.
Industry professional here: Loving going through this series, filling in the blanks in my knowledge. Greatly appreciated that you went to the trouble to upload them.
Professor Lindsey, thanks for these great explanations!! I am very excited that these pieces start to make sense to me! I was researching about consensus for my undergrad thesis project but with lots of doubts and holes. Your classes enlighten me and now I start to understand this topic. Greetings from a CS student in Perú.
Thanks for watching!
Thank you prof Lindsey for this valuable content !
One of the best in distributed system. Thank you mam.
Thanks for watching.
This was the only explanation that made sense to me, thank you 🙏
You are a great teacher. I watched distributed systems lecture series by Martin Klepmann but found it too abstract. You usage of examples really makes the concepts easier to understand.
Thanks for watching! Martin Kleppmann's videos are great; I hope you'll give them another try after watching mine!
Thank you, you explain very well the subject, helped me pass my DS exam!
Thanks for watching.
In lecture 4 you had mentioned that FIFO delivery is a subset of causal delivery. But in lecture 5, the set diagram shows it the other way around in which the set containing "executions observing FIFO delivery" are a super set of the set containing "executions observing causal delivery". My understanding is that FIFO delivery is a special case of causal delivery in which send of messages m1 and m2 happen on the same process; whereas in causal delivery send of messages m1 and m2 can happen on any process
The set of executions observing FIFO delivery is a superset of the set of executions observing causal delivery. In other words, every execution that observes causal delivery observes FIFO delivery, but not the other way around.
Hi Dr,
How do you account for node failures or additions in vector clock implementations?
Amazing lecture. Thank you so much
Thanks for watching!
Thanks a lot for this wonderful lecture 😇
Thank you for the well-detailed lecture. Could you please review my explanation? When we are speaking about FIFO delivery, do we mean only inter-process communication? We don't care about the order in which the same message is sent by another process (not included in IPC). When we are speaking about casual delivery, do we care only about the order messages sent from a certain process but received by any process? When we are speaking about the totally-ordered delivery, do we care only about the order messages sent by any processes and received by any processes? In other words, delivery guarantee is contingent on WHO is sending and WHAT is sent.
> We don't care about the order in which the same message is sent by another process (not included in IPC).
I'm not sure what you mean by "the same message" here. Two messages sent by different processes would not be considered "the same message". Anyway, FIFO delivery has to do with pairs of messages sent by the same process and received by the same process.
> When we are speaking about casual delivery, do we care only about the order messages sent from a certain process but received by any process?
Not exactly. Causal delivery has to do with pairs of messages that have a happens-before order. Messages sent by the same process do have a happens-before order, but they aren't the only pairs of messages that do. (For example, if Alice sends message m1 to Bob, and then Bob sends message m2 to Carol, then m1 happens before m2, even though m1 and m2 didn't come from the same sender.)
Finally, totally-ordered delivery has to do with pairs of messages delivered by the same process. It says that if a given process delivers two messages in a given order, then any other process delivering both will deliver them in that order as well.
@@lindseykuperwithasharpie I see, I understand it better, thanks a lot.
"Already part of TCP".
I asked many questions about FIFO over TCP to chatgpt, claude and gemini and none could answer what the professor explained.
The TCP specification (www.ietf.org/rfc/rfc793.txt) uses the words "ordered" or "in order" rather than "FIFO". I prefer to say "FIFO delivery" rather than "ordered delivery", because to me, "ordered" is ambiguous (*what* order?), but I'm in the minority there.
Prof @@lindseykuperwithasharpie The spec says TCP is "a highly reliable host-to-host protocol" i.e. one to one and then says "Multiple SENDs are served in first come, first served order, so the TCP will queue those it cannot service immediately." service=deliver, and further says "A natural way to think about processing incoming segments is to imagine that they are first tested for proper sequence number (i.e., that their contents lie in the range of the expected 'receive window' in the sequence number space) and then that they are generally queued and processed in sequence number order."
You are in minority because they may not say FIFO but their interface is FIFO. 😅
Exactly. It is FIFO; that's just not the word they use for it in the spec.
Hi!
@1:31:04 Did you assume that M1 occurs before M2? As from the Lamport diagram, one can't deduce that.
No, they're concurrent. If messages were totally ordered, then both processes would deliver m1 and then m2, or both would deliver m2 and then m1. Either would be a legitimate total order. (In the definition of total order, I'm using "m1" and "m2" as metavariables, not referring to these particular messages.)
I'm also wondering how these 3 deliveries are applied in the real world.
@lindseykuperwithasharpie Many thanks for your lectures. Can you please share some recomended reading on research papers as a follow up on this topic.
For vector clocks, Mattern's original paper "Virtual Time and Global States of Distributed Systems" (vs.inf.ethz.ch/publ/papers/VirtTimeGlobStates.pdf) is a good read. Even better, in my opinion, is Schwarz and Mattern's "Detecting Causal Relationships in Distributed Computations:
In Search of the Holy Grail", from a few years later (vs.inf.ethz.ch/publ/papers/holygrail.pdf).
Wouldn't bob back to carol make it (0,3,3) because it's a received event?
Not sure I understand your question, sorry.
At around 51:55, you mention TCP cant guarantee about message corruption, but I think it does (through the checksum calculations for the payload & re-requesting a packet in such a case). Pls correct me if i am wrong though.
Ah, yeah, so TCP does have a checksum mechanism; a corrupted message that you could detect this way would fall into the category of "authentication-detectable" Byzantine faults, which we can turn into an omission fault by dropping the message. But it isn't guaranteed, whereas TCP does indeed guarantee FIFO delivery (and reliable delivery). My point was that the FIFO and reliable delivery guarantees do not, by themselves, do anything to rule out arbitrary Byzantine behavior.
Thanks!
Hi except in the case of vacuously satisfying FIFO delivery, we ALWAYS need reliable delivery to satisfy FIFO delivery correct? If we are assuming the Omission fault model.
So in the Omission fault model, FIFO delivery implies Reliable delivery?
No, FIFO delivery and reliable delivery are distinct things. FIFO delivery is a safety property; it says that you never deliver messages out of FIFO order. You could drop all the messages on the floor and still satisfy FIFO delivery. Reliable delivery is a liveness property. It has nothing to do with the order in which messages are delivered.
@@lindseykuperwithasharpie Yes that is true. BUT in the case that the FIFO is non-vacuous, FIFO will will inherently do Reliable delivery right [ using ACK etc. ] ?....because if we do NOT get a middle sequence number, we will re-transmit to guarantee FIFO right?
FIFO delivery doesn't "do" anything. It's just a property that's either true or not true of an execution. It says nothing about how one would actually implement a mechanism that ensures that property.
@@lindseykuperwithasharpie Oh okay got it :)
I was confusing the "FIFO" concept with its implementation.
So for all practical purposes, the implementation of [ FIFO/Causal/Total-Order ] will need a Reliable delivery mechanism, IMHO!
Sure, I think it's fair to say that message ordering guarantees are considerably more useful if you also have reliable delivery. Reliable delivery by itself is also less useful without an ordering guarantee. In other words, both safety and liveness are important.
Best
Very good. Thank you!!!
Thanks for watching.
this lecture was fire, ty
Thanks for watching.
legends are watching this video day before exams
How'd your exam go?
@@lindseykuperwithasharpie excellent thank you so much you life saver
Hi Lindsey Kuper, How will the vector clock change if a node sends information to two other nodes simultaneously
Is it the same while receiving? If two nodes are sending information to a single node, how does vector clock change in that case?
The same message can have multiple recipients; that's called a multicast message. A multicast message will have the same vector clock regardless of recipient. The discussion of causal broadcast in the next couple of lectures is relevant here.
If a node receives two messages, they have to arrive in some order; they can't arrive simultaneously. So you'll have two separate receive events.
Thnk you mam
Thanks for watching.
1. FIFO delivery ensures that the order in which messages are sent by a process is the same as the order in which they are delivering by other processes.
2. Causal delivery ensures that messages with a causal relationship (i.e., one message happens before another) are delivered in the same order as they were sent.
3. Totally-ordered delivery ensures that messages are delivered in the same order on all processes.
FIFO delivery is a subset of causal delivery. However, totally-ordered delivery has nothing to do with FIFO or causal delivery.
FUA, lol, cracking me up.