It's 3.39AM here and I never thought that anyone can explain vector clock is such a simply and interesting way! I would like to say thank you from the bottom of my heart... 😃
I usually despise those who read presentations directly to the audience. But you, buddy, are an exception the way you explain, reveals a lot about your teaching experience. You deserve the likes and subscribers. thank you
One thing to understand here is "Total Order". Total order does not mean the actual order in which events have occurred. It only means that system as a whole agrees on some order independently. So the Causality here is for the total order. And hence Total order is NOT equal to happens before.
Timestamps built in take notes 8:08 lamport clocks example and what timestamps can tell us about event order, and if A causes B then B will have bigger timestamp, but there are limitations, just because lamport timestamp of A less than B doesn’t necessarily tell us that A happens before B. For that we need vector clocks 11:20 vector clocks 19:20 what timestamps of vector clock can tell us about event order 21:00 vector timestamp relationships and what they tell us about events
Thank you, Professor Kleppmann, for this wonderful series and for making it publicly available. This is gold for understanding distributed systems concepts! I have one question, though, regarding this lecture. I don't understand how vector clocks solve the original problem presented at the start of this lecture, i.e., resolving the correct order for the messages m1 and m2 received at User C. Since, by definition, logical clocks at a particular process are monotonic in nature, the vector clock for the event representing "m2 received at C" should be greater than the vector clock for the event representing "m1 received at C"; as we take the maximum of each vector-element to merge both the recipient and local vectors, as explained at 15:30. Therefore, I am not exactly sure how computing the vector clock for these two events at C helps to resolve the correct order. One way I can think of resolving the order would be to compare the vector clocks sent as part of the message instead (before merging the recipient and local vectors). But this requires storing the vector clocks for all the events (for message received events, we would need to store the recipient vector clock instead) and then comparing the recipient vector clock (whenever a message arrives) with that of all the earlier events for a particular process or user, and then rearranging the events and possibly reassigning the vector clocks for the rearranged events. I'm not exactly sure about this approach as it may cause some other effects that needs to be handled; I couldn't really find much regarding this elsewhere.
@Martin Thank you for the lecture. I don't understand how Lamport clock can give total order though. I don't think it is possible to order 2 events happening concurrently on 2 distinct nodes of the system using Lamport clock. We can use node name to disambiguate the timestamp but that doesn't give any guarantee of ordering, unless there's a guarantee on the flow of the events, like in case of leader-follower system. Can you please explain more?
Exactly my question too. In case the Lamport timestamps are same then lexicographic ordering of the node names won't necessarily give us the correct total order.
(Lamport) - What happens to the local t counter on a node when the node crashes or is rebooted ? Is it persisted to disk and synced between in-memory and disk every time an event occurs ?
Lamport clocks: How can a node order helps to uniquely indentify the event order if timestamps are same for two events. Is it always true that event will always flow thru to nodes in lexicographic order
Thanks for putting up these lectures. Very clear and concise. In logical clocks, how are the counters handled when the counter values become large (beyond maximum values for int/long)? This process has to be handled simultaneously across all the nodes correct?
Yes, you can check out cs.stackexchange.com/a/129175/41249 for more information. Basically we need some sort of consensus protocol to coordinate clock resetting.
Most protocols just make the integers so big that they are very unlikely to overflow in the lifetime of a system. For example, 64 bits would allow you to have 1 million events per second and still run for 500,000 years without overflowing.
@kleppmann Thank you Martin for an excellent explanation. But what if A will fail and try to send it's state after others gone forward, how do we know a real sequence of events of A on timeline with others?
Vector clocks have nice theoretical properties, but I can see some practical issues. For example, requiring that every node in the system stores information about the clocks of every other node seems to be prohibitively expensive as the number of nodes increases.
It depends. If the number of nodes is one hundred, assuming one 64-bit counter per node, you'd require about 800 bytes to store one vector (if you used an array with the number of nodes). This could be implemented through a map, which increases the required space but also increases flexibility and scalability. Sending this amount of data with every message might bloat your messages indeed, as it's over half an Ethernet packet's MTU. Vector clocks are often used in distributed databases to order requests (delete, update, read), so that you get a consistent state.
What happens if an unknown node joins the system? Do all clocks have to update via broadcast for example? And do we also have to update all stored timestamps in a database hence those became incomparable in that case?
Thank you Sir for such great fundamental series on the topic. I have a question - It is mentioned on slide 67 that if L(a) < L(b) does not imply a -> b, which makes sense. But then I am unable to get my head around the fact that Lamport timestamps can still be used to get total order as described in slide 68. Could you please help in clarifying this? Specifically, in the total order equation, why are we first checking for Lamport time stamps and if one is less than the other, conclusion is being made that a comes before b in total order.
What if say we stand at some particular time values at node a and b as 2a and 2b, and now when communication starts from b to a, they will have 3a and 3b values respectively, and at this point does it make sense to give node b bigger lamport value if we have initially assigned/assumed node b having greater value, it can be in both ways, but we know message has reached from b to a, ideally lamport of a should be greater than a, or this case does not exist, or we are assuming , communication always goes from lower nodes to higher nodes like it is shown from a to b to c etc
Thanks a lot for the great video. But I don't quite understand how it solves the initial problem at 0:59. Referencing the image at 0:59 and try to use Lamport time, m1 arrived at user C will have a Lamport time larger than m2 arrived at user C. And since both m2 and m1 arrived user C, so m2 -> m1 (as they occurred in the same node). So still user C cannot have a proper order of m1 and m2.
User A sends m1 with Lamport clock 1. User B receives m1 and updates its own Lamport clock to 2. Then User B sends m2 with Lamport clock 3. Finally, User C will receive m2 with clock 3, and after that, m1 with clock 1. The application running on User C will notice that, although m1 arrived after m2, it did not happen before m2, due to the Lamport clocks associated. So the application can rearrange the messages so that m1 is observed before m2.
@@jerrycheung8158 Right before m1 arrives at C, C has clock 4 (m2's clock, 3, plus 1). Then, m1 arrives with clock 1. C will know for sure that m2 cannot have happened before m1, because m2's clock is larger than m1's clock. Now, C will adjust its own clock to max(current C clock, m1's clock)+1, which is max(4, 1)+1 = 5.
@@vhscampos1 so combine with your first answer, are the messages order independent of the lamport clock? because m1 has a larger clock number than m2 at C
@@jerrycheung8158 The order of *delivery* to the application code at C is independent. So m2 is delivered before m1 even though it has a smaller Lamport clock. It's up to the application code at C to detect this and reorder the messages. The point is that, using Lamport clocks, the application code at C is able to detect this. It wouldn't be otherwise. If messages must be delivered in the "proper" order to begin with, a broadcast protocol must be used instead, e.g. causal order broadcast or total order broadcast.
I was a bit tricked-up by a sentence given by Lamport in "Time, Clocks and the Ordering of Events in a Distributed System". He says: > "Another way of viewing the definition is to say that a [happened-before] b means that it is possible for event a to causally affect event b". This is true though misleading. If you replase 'happened-before' with 'could have causally affected' then things are ok. But you cannot do the reverse. Eg. if you look at two lamport timestamps tA and tB, if tA < tB then it *is* possible that event A causally affected event B (assuming you know nothing about the topology of the system or what process each event occurred on). However saying tA 'could have causally affected' tB (which is true) is *not* the same as saying tA happened-before tB. tl;dr The happened-before relationship is more specific than just 'could have causally affected'. happened-before does mean 'could have causally affected' but 'could have causally affected' does not mean happened-before.
Not sure what you mean by this: "However saying tA 'could have causally affected' tB (which is true) is not the same as saying tA happened-before tB. " If an event A causes an event B, surely A must have happened before B. What am I missing in your comment?
I am little confused on your statement on "logical timstamps/lamport timestamps provides total order". if they provide total order why even bother about vector clocks? you clearly say that lamport timestamp cannot distinguish concurrent events so how can you call that a "total order"? Also when I put in "does lamport timestamp gives partial order or total order ?" in chatGPT it clearly says "partial order". What am I missing?
The reason is that the clock skew cannot be avoided at the point when the causality is decided. Even though the clocks are synchronized, they are not precise all the time, from my understanding.
you cannot use the comparison result of lamport clocks to determine the "happens-before" relationship, even after adding the name of machine to the clock.
So at [th-cam.com/video/x-D8iFU1d-o/w-d-xo.html] if m1 gets delayed on C then it will have (6,C) and m2 will have (5,C).. how does it guarantee the causality of m1/m2 at C?,
no no, you are understanding it wrong. m1 is an event shared only between Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
I wish my profesor had explained the concurency theory in similar way as you had. He has huge tendencies to overcomplicate staff by his fancy, unfriendly notations :(
It's 3.39AM here and I never thought that anyone can explain vector clock is such a simply and interesting way! I would like to say thank you from the bottom of my heart... 😃
4:38 am here 😁
I don't know who you are, but that's was the best explanation about l clocks, I've seen so far. Not so much info even in the wiki.
If I remember correctly, he's the author of CRDT
@@snowy0110 All the best to him. He is doing a great job.
He is a legend. look up Designing Data-Intensive Applications
He's the author of DDIA. Bible of distributed systems.
I usually despise those who read presentations directly to the audience.
But you, buddy, are an exception
the way you explain, reveals a lot about your teaching experience.
You deserve the likes and subscribers.
thank you
One thing to understand here is "Total Order". Total order does not mean the actual order in which events have occurred. It only means that system as a whole agrees on some order independently. So the Causality here is for the total order. And hence Total order is NOT equal to happens before.
Timestamps built in take notes
8:08 lamport clocks example and what timestamps can tell us about event order, and if A causes B then B will have bigger timestamp, but there are limitations, just because lamport timestamp of A less than B doesn’t necessarily tell us that A happens before B. For that we need vector clocks
11:20 vector clocks
19:20 what timestamps of vector clock can tell us about event order
21:00 vector timestamp relationships and what they tell us about events
Physical timestamps inconsistent with causality [0:11]
Logical vs. physical clocks [1:05]
Lamport clocks algorithm [2:46]
Lamport clocks in words [4:23]
L(a) (a⪯b)
Vector clocks [11:10]
(detail) [12:05]
Vector clocks algorithm [14:17]
Vector clocks example [16:04]
Vector clocks ordering [19:19]
Wow, first time listening to Cambridge University. Love it, both content and the British accent.
Thank you, Professor Kleppmann, for this wonderful series and for making it publicly available. This is gold for understanding distributed systems concepts! I have one question, though, regarding this lecture. I don't understand how vector clocks solve the original problem presented at the start of this lecture, i.e., resolving the correct order for the messages m1 and m2 received at User C. Since, by definition, logical clocks at a particular process are monotonic in nature, the vector clock for the event representing "m2 received at C" should be greater than the vector clock for the event representing "m1 received at C"; as we take the maximum of each vector-element to merge both the recipient and local vectors, as explained at 15:30. Therefore, I am not exactly sure how computing the vector clock for these two events at C helps to resolve the correct order. One way I can think of resolving the order would be to compare the vector clocks sent as part of the message instead (before merging the recipient and local vectors). But this requires storing the vector clocks for all the events (for message received events, we would need to store the recipient vector clock instead) and then comparing the recipient vector clock (whenever a message arrives) with that of all the earlier events for a particular process or user, and then rearranging the events and possibly reassigning the vector clocks for the rearranged events. I'm not exactly sure about this approach as it may cause some other effects that needs to be handled; I couldn't really find much regarding this elsewhere.
Excellent presentation. I read and understood the Lampert paper but this presentation is so much clearer.
@Martin Thank you for the lecture. I don't understand how Lamport clock can give total order though. I don't think it is possible to order 2 events happening concurrently on 2 distinct nodes of the system using Lamport clock. We can use node name to disambiguate the timestamp but that doesn't give any guarantee of ordering, unless there's a guarantee on the flow of the events, like in case of leader-follower system. Can you please explain more?
Exactly my question too. In case the Lamport timestamps are same then lexicographic ordering of the node names won't necessarily give us the correct total order.
Vielen Dank! Thanks Martin! Very clear explanation on Lamport and Vector logical clocks, inspired my lectures for CS from your explanation.
(Lamport) - What happens to the local t counter on a node when the node crashes or is rebooted ? Is it persisted to disk and synced between in-memory and disk every time an event occurs ?
Very helpful! Though I wonder, what if the number of nodes is dynamic when using a vector clock, and you persist events in a database?
Спасибо. Это превосходно!
Crystal clear
Lamport clocks: How can a node order helps to uniquely indentify the event order if timestamps are same for two events. Is it always true that event will always flow thru to nodes in lexicographic order
Great explanatory video. Thank you very much, this helps me a lot with an essay I have to write.
Thanks for putting up these lectures. Very clear and concise.
In logical clocks, how are the counters handled when the counter values become large (beyond maximum values for int/long)? This process has to be handled simultaneously across all the nodes correct?
Yes, you can check out cs.stackexchange.com/a/129175/41249 for more information. Basically we need some sort of consensus protocol to coordinate clock resetting.
@@yusongshen5016 Thank you!
Most protocols just make the integers so big that they are very unlikely to overflow in the lifetime of a system. For example, 64 bits would allow you to have 1 million events per second and still run for 500,000 years without overflowing.
@@kleppmann thank you!
What happens to vector/lamport clocks system when nodes are frequently added and leaving the system?
I suppose that they values are just updated when event with t will occur
@kleppmann Thank you Martin for an excellent explanation. But what if A will fail and try to send it's state after others gone forward, how do we know a real sequence of events of A on timeline with others?
Best explanation on logical clocks.
Where lamport and vector timestamp used in real-time application or distributed system?
Does Automerge use vector-clocks, Lamport clocks, or something different to determine causality?
Vector clocks have nice theoretical properties, but I can see some practical issues. For example, requiring that every node in the system stores information about the clocks of every other node seems to be prohibitively expensive as the number of nodes increases.
It depends. If the number of nodes is one hundred, assuming one 64-bit counter per node, you'd require about 800 bytes to store one vector (if you used an array with the number of nodes). This could be implemented through a map, which increases the required space but also increases flexibility and scalability. Sending this amount of data with every message might bloat your messages indeed, as it's over half an Ethernet packet's MTU. Vector clocks are often used in distributed databases to order requests (delete, update, read), so that you get a consistent state.
What happens if an unknown node joins the system? Do all clocks have to update via broadcast for example? And do we also have to update all stored timestamps in a database hence those became incomparable in that case?
Thank you Dr. Matin!
Thanks Martin. Love your efforts and work, and ofcoure the awesome book : Designing data intensive application.
At 7:09, why does m2 not increment the timestamp to 4 at B when generated and then gets incremented to 5 when sent (6 when received at 6)?
When B receives 2 from A, it increments it to 3 for the receiving event. then B increments 3 to 4 for sending event.
Would atomic clock/TrueTime replacing the need to use a logical clock? (Assuming this is under an enterprise system)
Thank you Sir for such great fundamental series on the topic.
I have a question -
It is mentioned on slide 67 that if L(a) < L(b) does not imply a -> b, which makes sense.
But then I am unable to get my head around the fact that Lamport timestamps can still be used to get total order as described in slide 68.
Could you please help in clarifying this? Specifically, in the total order equation, why are we first checking for Lamport time stamps and if one is less than the other, conclusion is being made that a comes before b in total order.
if a and b are concurrent, we might as well order them by the node name in which they occur
What if say we stand at some particular time values at node a and b as 2a and 2b, and now when communication starts from b to a, they will have 3a and 3b values respectively, and at this point does it make sense to give node b bigger lamport value if we have initially assigned/assumed node b having greater value, it can be in both ways, but we know message has reached from b to a, ideally lamport of a should be greater than a, or this case does not exist, or we are assuming , communication always goes from lower nodes to higher nodes like it is shown from a to b to c etc
Thanks a lot for the great video. But I don't quite understand how it solves the initial problem at 0:59. Referencing the image at 0:59 and try to use Lamport time, m1 arrived at user C will have a Lamport time larger than m2 arrived at user C. And since both m2 and m1 arrived user C, so m2 -> m1 (as they occurred in the same node). So still user C cannot have a proper order of m1 and m2.
User A sends m1 with Lamport clock 1. User B receives m1 and updates its own Lamport clock to 2. Then User B sends m2 with Lamport clock 3. Finally, User C will receive m2 with clock 3, and after that, m1 with clock 1. The application running on User C will notice that, although m1 arrived after m2, it did not happen before m2, due to the Lamport clocks associated. So the application can rearrange the messages so that m1 is observed before m2.
@@vhscampos1 thanks for the reply. In this case, how will C adjust the local counter when m1 arrived?
@@jerrycheung8158 Right before m1 arrives at C, C has clock 4 (m2's clock, 3, plus 1). Then, m1 arrives with clock 1. C will know for sure that m2 cannot have happened before m1, because m2's clock is larger than m1's clock. Now, C will adjust its own clock to max(current C clock, m1's clock)+1, which is max(4, 1)+1 = 5.
@@vhscampos1 so combine with your first answer, are the messages order independent of the lamport clock? because m1 has a larger clock number than m2 at C
@@jerrycheung8158 The order of *delivery* to the application code at C is independent. So m2 is delivered before m1 even though it has a smaller Lamport clock.
It's up to the application code at C to detect this and reorder the messages. The point is that, using Lamport clocks, the application code at C is able to detect this. It wouldn't be otherwise.
If messages must be delivered in the "proper" order to begin with, a broadcast protocol must be used instead, e.g. causal order broadcast or total order broadcast.
I was a bit tricked-up by a sentence given by Lamport in "Time, Clocks and the Ordering of Events in a Distributed System". He says:
> "Another way of viewing the definition is to say that a [happened-before] b means that it is possible for event a to causally affect event b".
This is true though misleading. If you replase 'happened-before' with 'could have causally affected' then things are ok. But you cannot do the reverse. Eg. if you look at two lamport timestamps tA and tB, if tA < tB then it *is* possible that event A causally affected event B (assuming you know nothing about the topology of the system or what process each event occurred on). However saying tA 'could have causally affected' tB (which is true) is *not* the same as saying tA happened-before tB.
tl;dr The happened-before relationship is more specific than just 'could have causally affected'. happened-before does mean 'could have causally affected' but 'could have causally affected' does not mean happened-before.
Not sure what you mean by this: "However saying tA 'could have causally affected' tB (which is true) is not the same as saying tA happened-before tB. "
If an event A causes an event B, surely A must have happened before B. What am I missing in your comment?
Really Lucid explanation! Thank you!
great job! well explained!
Why is it called a logical clock instead of an ordinal clock (ordinal time and interval time seems appropriate to describe the distinction)?
i have a questione , is concurent events and independantes events the same thing
Really good stuff👍👍👍
I am little confused on your statement on "logical timstamps/lamport timestamps provides total order". if they provide total order why even bother about vector clocks? you clearly say that lamport timestamp cannot distinguish concurrent events so how can you call that a "total order"? Also when I put in "does lamport timestamp gives partial order or total order ?" in chatGPT it clearly says "partial order". What am I missing?
Nice explanation!
very beautiful explanation❤
Really appreciate your work! Thanks buddy!
Can't you define a total order using Lamport's timestamps by only using the rule (a
Can anyone explain how synchronized timestamps solution does not capture causality?
The reason is that the clock skew cannot be avoided at the point when the causality is decided. Even though the clocks are synchronized, they are not precise all the time, from my understanding.
Thank you so much, perfect explanation.
Request @TH-cam to add facility to like a video more than once. I'd like to do so for this one.
Such a great video, thank you so much. You're awesome!
Danke für deine Hilfe, meine Abgabe konnte ich damit bearbeiten (Y)
excellent stuff ! thank you very much!!!!!!!
All logical clocks I have seen so far require a central coordinator. Looking for a truly distributed logical clock algorithm.
非常感谢您！
i wondering about version vector, too. !!
Thank you, very clear :)
Then (3,A) < (3,B). However, the time-line suggests (3,B) happened before (3,A)
you cannot use the comparison result of lamport clocks to determine the "happens-before" relationship, even after adding the name of machine to the clock.
(3,A) < (3,B) doesn't imply (3,A) happens before (3,B), conversely it's true.
@@yihanwu3823 But if node A is given more priority than node B, then holds true to maintain total ordering.
So at [th-cam.com/video/x-D8iFU1d-o/w-d-xo.html] if m1 gets delayed on C then it will have (6,C) and m2 will have (5,C).. how does it guarantee the causality of m1/m2 at C?,
no no, you are understanding it wrong. m1 is an event shared only between Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
I wish my profesor had explained the concurency theory in similar way as you had. He has huge tendencies to overcomplicate staff by his fancy, unfriendly notations :(
I love you Martin
11:40 you tube
epic
I don't know who you are, but that's was the best explanation about l clocks, I've seen so far. Not so much info even in the wiki.