System model:

• Contains a collection of processes, which can communicate reliably over one-to-one channels. 
• Processes may fail only by crashing.
• The processes are members of groups.
• To simplify, processes is member of at most one group at a time.
• Operation multicast(g, m) sends the message m to all members of the group g of processes. 
• Operation deliver(m) that delivers a message sent by multicast to the calling process.
• Every message m carries the unique identifier of the process sender(m) that sent it and the unique destination group identifier group(m). 
• Assume that processes do not lie about the origin or destinations of messages. 

Basic multicast

• A correct process will eventually deliver the message, as long as the multicaster does not crash. 
• Straightforward way to implement B-multicast is to use a reliable one-to-one send operation:

Reliable multicast

• All correct processes in the group must receive a message if any of them does. 
• Integrity: A correct process p delivers a message m at most once. 
• Validity: If a correct process multicasts m, then it will eventually deliver m.
• Agreement: If a correct process delivers message m, then all other correct processes in group(m) will eventually deliver m. 
• If a process that multicasts a message crashes before it has delivered it, then it is possible that the message will not be delivered to any process in the group; but if it is delivered to some correct process, then all other correct processes will deliver it. 
  
  

  Figure 6.9: Reliable multicast algorithm
  
  

• The algorithm satisfies the validity property, since a correct process will eventually B-deliver the message to itself.
• By the integrity property of the underlying communication channels used in B-multicast, the algorithm also satisfies the integrity property.
• Agreement follows from the fact that every process B-multicasts the message to the other processes after it has B-delivered it. 
• If a process does not R-deliver the message, then this can only be because it never B-delivered it. 
• That in turn can only be because no other correct process B-delivered it either; therefore none will R-deliver it. 

Uniform properties

• The agreement above refers only to the behaviour of correct processes – processes that never fail.
• If a process was not correct and crashed after it had R-delivered a message, since any process that R-delivers the message must first B-multicast it, it follows that all correct processes will still eventually deliver the message. 
• Uniform agreement: If a process, whether it is correct or fails, delivers message m, then all correct processes in group(m) will eventually deliver m. 
• It is useful in applications where a process may take an action that produces an observable inconsistency before it crashes. 
  

Ordered multicast

• The basic multicast algorithm delivers messages to processes in an arbitrary order, due to arbitrary delays in the underlying one-to-one send operations. 
• To simplify, the orderings assume that any process belongs to at most one group only. 
• Common ordering requirements:
  • FIFO ordering: If a correct process issues multicast(g, m) and then multicast(g, m’), then every correct process that delivers m’ will deliver m before m’. 
  • Causal ordering: If multicast(g, m) -> multicast(g, m’), where -> is the happened-before relation induced only by messages sent between the members of g, then any correct process that delivers m’ will deliver m before m’.
  • Total ordering: If a correct process delivers message m before it delivers m’, then any other correct process that delivers m’ will deliver m before m’. 
• The definitions of ordered multicast do not assume or imply reliability. 
  
  

  Figure 6.11: Total, FIFO and causal ordering of multicast messages
  
  
  

Overlapping groups

• The preceding definitions considered only non-overlapping groups. 
• Global FIFO ordering: If a process issues multicast(g, m) and then multicast(g’, m’), then every correct process in g ∩ g’ that delivers m’ will deliver m before m’. 
• Global causal ordering: If multicast(g, m) -> multicast(g’, m’), where -> is the happened before relation induced by any chain of multicast messages, then any correct process in g ∩ g’ that delivers m’ will deliver m before m’. 
• Pairwise total ordering: If a correct process delivers message m sent to g before it delivers m’ sent to g’, then any other correct process in g ∩ g’ that delivers m’ will deliver m before m’.
• Global total ordering: Let ‘<‘ be the relation of ordering between delivery events. We require that ‘<‘ obeys pairwise total ordering and that it is acyclic.