We start by introducing the idea of a group membership service that uses quorum updates and 2/3PC to manage group views. Since we want to cover this quickly we present the protocol in less detail than the book uses.
Once we have group views, it is easy to implement various forms of reliable multicast and this lecture now takes the first step by introducing an fbcast protocol.
The treatment tracks Chapter 14 of the book, but to keep the length of the lecture manageable we omit much of the detail..
1) First, we implement the group membership service. To explain this idea to the class, I point out that to be registered in CS514, they need to go through the Cornell registrar, who sends me the classlist and updates it periodically. They could get this list too if they knew how to ask. So: the registrar's office is like a GMS for CS514.
But who works in that office? They have a whole protocol for filing vacancies, etc. That's like a GMP: it governs the way that the GMS tracks its own membership. We don't want it to partition (e.g. form two logically distinct GMSs).
2) The protocol is basically a 2PC run by the oldest GMS member (the leader), but one that can't abort -- it only commits, except that it can't do so until a majority (or more) processes have acked the proposed view. If some processes don't ack and we time out, they end up getting dropped from the view by a subsequent protocol round that runs overlapped with the commit phase. E.g "I propose to drop process x from the current view {p,q,r,s,x}. (I'm p). Perhaps q and r send "OK" but s dies and we timeout. Then I can "commit {p,q,r,s} but simultaneously start a proposal to drop s.
3) The notion of shunning is fairly basic: if I think x has failed, I cut my channels to x and if I talk to you you cut your channels to x, too. So x is ostracized (if it was actually up). Anyone it manages to contact sends back "sorry, my records show that you are deceased!". x is forced to do a failure / restart to rejoin the system. We do this because the system may have taken various roles away from x: it is no longer the primary server, or no longer owns the ATC sector, etc. So it "fails" (tells the user it has lost contact with the group), then can rejoin -- in a new set of roles.
4) Majority consent is needed. If a group has just 2 members, for example, it can't tolerate the failure of 1 of them unless we can somehow get proof that the other has really failed -- this is the cost of avoiding any risk of partitioning (split brain behavior). No majority? Then the process running the protocol must wait or perhaps declare *itself* to have failed!
5) We add one phase if the leader died; during it the new leader finds out what the old one was doing and thus is able to finish up the pending view changes and add the new view that drops the old leader to the end of the sequence.
---
This covers the GMP/GMS. Now, using it, we can build a reliable multicast. Here's how
1) Send the multicast unreliably, using some sort of retransmit logic to deal with lost packets (acks/nacks, for example). Out of band, or piggybacked on other multicasts, when a message becomes stable, tell everyone; they can then discard saved copies that they maintained for use in... step 2
2) If a sender fails, the GMS reports a new view. DON'T TELL THE APPLICATION ABOUT IT YET! Instead, everyone echoes any unstable messages they still have. This includes multicasts received indirectly. Once everyone has seen everyone else's unstable multicasts and echoed all of them, everyone sends a "done" market, much like the Chandy/Lamport cut algorithm. Once you have a done marker from everyone, you can tell the application about the new view. (If someone fails you don't need a done marker from them, but you do need an extra round of flushing).
For example, maybe p failed after sending a multicast that only reached q. New view reports this, and q starts flushing but perhaps q fails after sending just one copy, to r. But r echoes out not just unstable messages it already had, but this new one that was received via q.
As long as nobody deliberately scrambles the order of messages, this protocol is fifo if member-to-member communication is fifo.
3) Now we have a virtually synchronous fbcast protocol and also a framework for doing state transfer: when delivering the new view, you can also ask for a group's leader to checkpoint its state, send that to a joining member, and the new guy can load the state to initialize itself.