CSE138 (Distributed Systems) L4: vector clocks, FIFO/causal/totally-ordered delivery
Vložit
- čas přidán 11. 04. 2021
- 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.edu/~lkuper/
Course website: decomposition.al/CSE138-2021-03
Schedule of topics: decomposition.al/CSE138-2021-0... - Věda a technologie
This video saved my life before distributed system midterm exam. Tons of Thanks.
This was the only explanation that made sense to me, thank you 🙏
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.
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!
Thanks a lot for this wonderful lecture 😇
One of the best in distributed system. Thank you mam.
Thanks for watching.
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, you explain very well the subject, helped me pass my DS exam!
Thanks for watching.
Amazing lecture. Thank you so much
Thanks for watching!
Very good. Thank you!!!
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.
Thanks!
this lecture was fire, ty
Thanks for watching.
Best
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.
Thnk you mam
Thanks for watching.
Hi Dr,
How do you account for node failures or additions in vector clock implementations?
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.
FUA, lol, cracking me up.
@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).
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.)
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.
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.
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.
I'm also wondering how these 3 deliveries are applied in the real world.
legends are watching this video day before exams
How'd your exam go?
@@lindseykuperwithasharpie excellent thank you so much you life saver