Group Communication in Amoeba and its Applications
Kaashoek, Tanenbaum, Verstoep

What is Amoeba?
What's a distributed operating system?

what apps do they have for total order multicast?
  one example: directory server
  what does it do?
  why does it need multicast?
  why does it need total order?

how do they implement total ordering?
  sequencer!

what if a receiver misses pkt from sequencer?
  everyone keeps copies for a while, can request re-send

how does the sequencer know when it can stop storing old msgs?
  how do the other nodes know?

what if sequencer sends one copy, then sequencer and dst fail?
  there's yet another phase that ensures r receive before acting
  and thus that r have a copy to update recovering nodes

state:
  X: sequencer keeps next seq#
  H: every node keeps a history of recent messages
     also used to hold out-of-order messages?
  S: every node remembers last seq# delivered to process
     so S+1 is first non-received seq#

so the complete protocol:
  1. sender sends to sequencer
  2. sequencer assigns seq#, broadcasts to all
  3. nodes send ACKs for this seq#
  4. sequencer collects r ACKs, broadcasts accept message
  5. everyone sends sequencer their S (can be lazy)
  6. sequencer takes min(S), re-broadcasts (can be lazy)
     now everyone can discard saved msgs <= min(S)

What is the Amoeba directory server?
  directory is name->capability mapping
  capabilities refer to e.g. files
  3 servers, have identical replicas of directory

if no crashes, how does dir server use multicast?
  1. client sends req to server S1
  2. S1 multicasts to the group
  3. S1 replies to client when r=2 group members see it
  total order keeps the replicas in sync

what if a server crashes and stays down?
  remaining two check for majority, keep going
  what about r=2???

why the check for majority?

what has to happen if that server re-starts?
  needs to re-build its state
    perhaps process the messages it missed
    or get complete copy of state from another server
  if two other servers were operating continuously
    get their message history or state
  how to find the server with the latest state?
    how do you even know that server is among those you're talking to?
  suppose you can talk to all servers
    how to agree on which crashed last?
    which has the highest recorded sequence number?
    if crashes were ordered, whose crash wasn't observed?