Message Ordering

Multicast receiver algorithm decides when to deliver a message to process. There are three actions available:

1. Deliver immediately to the application
2. Place on a hold-back queue to deliver lately (when some other messages should be received before the one held back)
3. Discard

Multicast message ordering determines the order of multicast delivery at different processes in the group. There are three popular flavors implemented by several multicast procols:

1. FIFO ordering
2. Causal ordering
3. Total ordering

FIFO

If $m_1$ and $m_2$ are multicast messages by the same node, and $m_1$ is multicasted before $m_2$$\text{multicast}(m_1)\rightarrow\text{multicast}(m_2)$, then $m_1$ must be delivered before $m_2$ at all receivers.

Multicasts by different nodes can be delivered at different order.

Valid orders: $(m_2,m_1,m_3),\ (m_1,m_2,m_3),\ (m_1, m_3, m_2)$

Implementation:

• Each sender puts the sequence number into message, incrementing it after sending the message and keep the copy of un-ack. messages
• Each receiving process keeps track of sequence numbers of all senders. When a message is received, they reply with ack. message to inform about the reception. If message has expected seq. no., then deliver immediately; if message seq. no. is higher than expected, store in the queue; if lower — discard.

Causal ordering

Multicast messages that are causally related must be delivered in the same causality order, at all receivers if $\text{multicast}(G, m_1)\rightarrow\text{multicast}(G,m_2)$, then every process that delivers $m_2$ will have delivered $m_1$.

Concurrent messages can be delivered in either order.

Valid orders are: $(m_1,m_2,m_3),\ (m_1, m_3, m_2)$