Distributed Systems 4.2: Broadcast ordering
Vložit
- čas přidán 9. 07. 2024
- Accompanying lecture notes: www.cl.cam.ac.uk/teaching/212...
Full lecture series: • Distributed Systems le...
This video is part of an 8-lecture series on distributed systems, given as part of the undergraduate computer science course at the University of Cambridge. It is preceded by an 8-lecture course on concurrent systems for which videos are not publicly available, but slides can be found on the course web page: www.cl.cam.ac.uk/teaching/212...
might be one of the best series that I've seen on distributed systems
Very clear and well explained. I really appreciate you putting these up.
10:40 causal broadcast (review what causality between events is)
Total order broadcast is a step up from causal broadcast. In total order all the nodes deliver messages in some agreed upon order. Nodes can “hold back” received messages, delay delivering them to the application until the message that’s supposed to come before it arrives.
Who decides on the total order of messages?
Incredibly well made video. Good job and thank you!
Excellent explanation!
Great video, thank you :)
For total order broadcast, does it need to select a node to be an "observer"? If it doesn't, how can we know which node is getting the correct order? If it does, do other nodes need to wait until that "observer" returns the valid order to guarantee the order?
Broadcast protocols
system model from lecture 2 [2:21]
Receiving versus delivering [3:39]
Application ⇄ Broadcast algorithm (middleware) ⇄ Network
Forms of reliable broadcast [5:04]
FIFO broadcast [5:58]
Causal broadcast [9:00]
Total order broadcast (1) [11:39]
Total order broadcast (2) [13:48]
Relationships between broadcast models [15:27]
Thank you!
thank you very much
Thank you
Hi, The concept is easy to follow up, but I'm curious how to guarantee, for example, total order delivery. I can't come up with an simple approach to do this, does it involve consensus algorithm, e.g., Raft or Paxos?
I believe that's covered in the next video in this series.
See video 6.2 in this lecture series, on the Raft consensus algorithm.
If a system starts with gossip protocol to disseminate messages, then relay to a byzantine reliable broadcast, finally progress into consensus protocol which has O(1) time complexity. What should be the overall time complexity for this system? Thx.
I think the types of broadcast ordering they are like talking about types of consistency model. Is that right? I'm not sure just guessing
I understand that there are use cases for this broadcast protocols, but I find it hard to grasp under which situation I would use causal broadcast? How do you know some messages are causally related if they are originated from different nodes? Some examples would come in handy.
Thanks a lot
You can't tell. That's why you have to consider the worst case, that everything that happens before is related.
Take my comment here for example, it is causally related to yours; I wouldn't have submitted it if I were not aware of your comment. Ok, but what if to write this down (sending a message) I'm being based on some other comment that I saw on the page (messages that were delivered to me)? You'll never be sure, so you have to consider the worst case, that I could be writing this based on every other comment I could see until I submitted.
If you don't consider my comment causally dependent of all the other comments that I already saw (messages that were delivered to me), it would be possible (under the protocol) for me to mention here another comment that I saw, and you to be seeing my mention without even acknowledging the existence the mentioned comment itself (because it was not delivered to you yet). That would be a causal violation.
Hint: timestamps. The long answer is in later videos in this series.
See lecture 4.1 in this series on what it means to be causally related.
I agree that "real-world" examples would come in handy. Coming back here after having watched some of the subsequent videos to leave one example that came to my mind.
Blockchains run a total broadcast ordering of txs (the block miner/proposer, who is the temporary leader, decides on a total ordering for the next block, and broadcasts this ordering to all other nodes). However, there are many transactions in a given block that are totally unrelated and touch entirely separate regions of the global blockchain virtual machine memory. This is why certain new consensus protocols use DAGs instead of building a chain: txs that aren't causally related should be allowed to be included in whatever order and propagated independently to other nodes. This allows optimizing network bandwith, as well as paralellizing VM execution of those transactions (those are aren't causally related can be processed in parallel).
If a FIFO-total order multicasts implies causality, why are there algorithms for fifo-causal order multicasts?
I don't think "FIFO-causal" is a thing, because causal is stronger than FIFO. Perhaps, you meant "causal-total ordering"? Seems like "causal-total ordering" should be a thing, but it doesn't get mentioned for some reason. Perhaps, someone mistakenly decided that "FIFO-total ordering" is the name that should be applied to a system that is both causal and totally ordered? This would make the last slide make more sense to me, because I don't think FIFO-total order is stronger than causal.
I don't understand why FIFO-total order is causal tho... Total order just means that all nodes agree on the order of delivery. FIFO just means that messages sent by N_i are delivered in the same order that they were sent. So, putting these two together, any interleaving of messages by different notes can be FIFO total order as long as all nodes (magically) agree. But some interleaving are not causal. Am I missing something here??
Exercise 15 in the lecture notes asks you to prove that FIFO-total order implies causal order. If you want the solution notes for the exercises, email me (firstname at lastname dot com) and I can send them to you. (I don't put the solution notes online because I don't want the students to just copy them without thinking for themselves.)
My understanding: If m1 happens before m2, then this implies that m1 is delivered on B before m2. Therefore, FIFO + TO ensures that messages are delivered in m1, m2, m3 on all nodes i.e causal order. If m1 and m2 are concurrent, three causal orderings are possible i.e m1, m2, m3 or m2, m1, m3 or m1, m3, m2. FIFO + TO will produce one of these on all nodes. i.e FIFO + TO produces a causal order on all nodes. A simple causal order could have any of the 3 orders in each node. So, FIFO + TO is stronger than causal order. The key observation is the distinction b/w delivery vs reception of a message. Timestamps get updated only when the message is delivered to the application.
@kleppmann If my answer is correct, I'm happy to delete my comment to not be a detriment to the learning experience of other students.
Why total order is not strong than FIFO order?
Total order just means that all nodes deliver the messages in the same order; that order does not have to match the order in which they were sent. In practice, most algorithms that provide total order also provide FIFO order though.
Hi Martin. I was wondering why you don't mention the CATOCS (Causal And Totally Ordered Communication Systems) debate started by Cheriton and Skeen's "Understanding the Limitations of Causally and Totally Ordered Communication" paper. Is it because it's too complicated? Or because you find it uninteresting? Or you didn't know about it?
my teacher uses the same slides as yours
Love from Pakistan ❤️
This is Never my fave topic. Why does a node upon getting a message delivers it to itself? This is making me confused. What am I missing here?
It's just an abstraction. We are keeping the underlying network's responsibility as point-to-point links, so we don't have the functionality to ask the network to just broadcast a message from a node. That responsibility is separated to the broadcast layer/middleware, and it wants to deliver the messages to the application(which is another layer built on top of the broadcast layer) in causal order, so it might have to wait to deliver the message broadcasted at time t2 before delivering message broadcasted at time t1, even though m(t2) might have arrived at the receiver's broadcast layer before m(t1). Hope that helps!
@@shoumikghosal your explanation was useful, I wasn't paying attention around 3:43
Because the application might want/expect delivery order on one node to be "similar" to delivery order on other nodes. In order to achieve different kinds of "similarity", hold back might be required. Examples are showed in the second half of this video.
gutes video, aber dieser deutsch-britische akzent ist grauenhaft
kann dem gar nicht zustimmen, seine Aussprache ist phänomenal.....!
Und so ein Lob verteile ich äußerst selten....
Sonst reagiere ich auch extrem empfindlich auf deutschen Akzent, aber hier ist man definitiv bei der falschen Adresse