Reliable multicast properties, algorithm

Multicast sends one message to a group of processes. Reliable multicast ensures that the message is delivered to all correct members of the group (or to none), despite message loss or process failure.

Properties

1. Integrity: a correct process delivers a message at most once, and only if it was multicast by a member of the group.
2. Validity: if a correct process multicasts a message m, it eventually delivers m itself.
3. Agreement: if a correct process delivers m, then all other correct processes in the group eventually deliver m. Together, validity and agreement mean that if a correct sender multicasts, every correct member gets the message. Stronger orderings can be added optionally: FIFO, causal and total order.

Algorithm 1: reliable multicast over basic (unreliable) multicast, using acknowledgements

Each process p keeps a sequence number $S^p_g$ for the next message it sends to group g, and, for every process q, $R^q_g$ = the sequence number of the latest message it has delivered from q.

• R-multicast(g, m) by p: attach $S^p_g$ and the piggybacked acknowledgements ($R^q_g$ for all q), B-multicast to g, then increment $S^p_g$.
• On B-deliver(m) at q from p with sequence number S (q compares it with its own $R^p_g$):
  • if S = $R^p_g$ + 1: R-deliver m and increment $R^p_g$;
  • if S > $R^p_g$ + 1: put m in the hold-back queue and send a negative acknowledgement (NACK) for the missing messages;
  • if S ≤ $R^p_g$: discard it (duplicate).
• If the piggybacked acknowledgements show that q has missed some message, q requests retransmission from the sender (or from any process that holds it).

Algorithm 2: reliable multicast over reliable one-to-one channels (eager)

 on initialisation: received = {}
 R-multicast(g, m):  B-multicast(g, m)   // includes sender
 on B-deliver(m) from sender s:
     if m not in received:
         received = received + {m}
         if s != me: B-multicast(g, m)
         R-deliver(m)

Each process re-multicasts the message the first time it sees it, so if the sender crashes after reaching even one correct process, all correct processes still get it. Cost: O(N²) messages for a group of N.

Used for: replicated databases, group communication toolkits (ISIS), event notification and file distribution.