Distributed Systems 4.3: Broadcast algorithms
Vložit
- čas přidán 5. 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...
Broadcast algorithms
directly [0:28]
reliable link
node may crash
Eager reliable broadcast [1:46]
Gossip protocols [3:05]
FIFO broadcast algorithm [5:18]
Causual broadcast algorithm [7:10]
(deps =T from every node
Thanks for putting theses lectures online. This is amazing!
amazing. i remember starting the coursera distributed algorithms course but when they went over the algorithms, i never understood the context for any of them. this series is very concise about all the fundamental details while stringing together topic after topic
Well, it's the most complex 13 minutes in my education... Anyway, thanks a lot for the great compaction of complex algorithms into a single short video.
You are so elaborate and precise .. thanks for sharing 🙏
Thanks for your lecture on distributed systems, it's amazing. For this one I have a suggestion: I think renaming 'delivered' to 'to_be_delivered' would make the algorithm easier to understand.
Thanks Prof. Kleppmann.
Awesome lectures!
Great explatiom man underrated
Thanks for the wonderful lectures!
A minor question about the causal broadcast algorithm. On the receiving part, is it true that when the receiver found a (sender, deps, m) from its buffer, if the deps < delivered, it's actually not the first time the receiver received this tuple? In that case, the receiver will just remove it from the buffer and won't change the status of the delivered list.
Thx for excellent video and explanation. How about total order Broadcast vs Atomic Broadcast?
I have a question regarding the two different implementations that are outlined for Total Order Broadcast. If you use the single leader approach, the total order is not causally consistent. But if you use the Lamport clocks approach, it seems to me that this total order would be causally consistent (ie if you use Lamport clocks to implement total order broadcast, you actually get FIFO-total order broadcast.). Is this correct or am I missing something here?
Is the Lamport clocks approach to do TO broadcast equivalent to consensus?
Exercise 14 FIFO-total order broadcast using Lamport clocks，where can I discuss it？Lamport clocks approach has a problem 'how do you know if you have seen all messages with timestamp < T', need to be solved in this exercise?
Mr. Kleppmann I would like to ask you a question:
in causal broadcast algorithm, receiver doesn't have (sender, delivered[sender], m) ∈ buffer in while condition, can it be successful to be FIFO?
Because I see that you put vector-clock-like condition instead, but how does a machine proceed to receive message sequentially once it crashed?
Thank you!
Can someone explain me what notation(or pseudocode) is used here? I'm struggling do understand some parts.
In 11:20 we talk abou total order broadcasting with single leader, but this doesn't guarantee FIFO or causal right? Do we need to have an additional check on the leader, like for example making each follower send in it's i,dep,m array and also run the causal broadcast algorithm at the same time?
It seems to me like the lamport clocks approach solves the problem of making it FIFO total order automatically w/o additional work though. It however has an additional problem: since we need to wait for one more update before doing previous updates: we're guaranteed to have clients making updates on stale info
causal broadcast: "if a broadcast request X at node A originates before (happens before) broadcast request Y at node B, the delivery of X must happen before Y at all nodes."
we can prove the above holds for total order broadcast protocol using a single leader given
1) the “total-order-broadcast” is sent to the leader from the originator in a FIFO channel.
2) the leader has to “FIFO-broadcast” in the same order it received the “total-order-broadcast” requests.
Hint:
case 1 node A != node B
In this case, the causality path from request X to request Y should involve the leader receiving X, which implies the leader receives X before Y.
case 2 node A = node B
In this case, since the link from node (A=B) to leader is FIFO, leader receives X before Y.
at 12:39 why do we need to wait for timestamp > T for every node ?
I couldn't understand Total order broadcast algorithm with Lamport Clocks approach.
It doesn't make sense to use Lamport timestamps to order messages where nodes are more then 2. And you can't ensure global FIFO (first in first out), you can ensure it only between 2 nodes. which brings me to think that nodes can't prioritize between parallel/concurrent events.
The answer is that Lamport clock provides Total ordering, when numbers are the same node Names are compared...
So does the lamport clocks approach lead to a FIFO total order broadcast? To me it looks like the order of message deliveries is sort of round-robin. which essentially implies that it is FIFO.
OK, I looked closely at video again...only first-time message recipients rebroadcast...now the animation makes sense in terms of network message propagation. Still stuck on "randomly chosen nodes" in the network. The nodes chosen in the animation look like randomly chosen neighboring nodes, not truly random nodes.
how does the gossip protocal know if all the nodes got the message? does a coordinator have to be here to keep checking the status?
In an asynchronous system, where messages take an arbitrarily long time to transit, there is no way.
in gossip protocol, the node sends out a new message only the first time it receives the message; so if you received the same message before, you do not need to choose new nodes to gossip the message anymore. The stop condition is that all nodes received a copy of the message. How many hops? The diameter of the network topology.
@@andycjwu thanks, a crystal clear explaination
4:55 I wonder how was this probability calculated? Is it really high probability that eventually the message will reach all nodes?
check out Cloud computing concepts part 1 on coursera or check the paper on gossip. you will need to know integral calculus to reach the final probability figure.
Martin, whats your favorite aspect of long hair? As a fan, I must know!
1:05 implementing broadcast protocol in a naive way is not fault tolerant, if node A crashes then not all nodes will have gotten the message only some