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
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.
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.
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?
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.
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?
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.
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.
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!
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.
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.
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.
