Multicast

Introduction

Deliver and Receive

• Receive: queuing of arriving message in intermediate buffer (e.g., network interface buffer)
• 收到信息了, 放到buffer里排队处理

• Deliver: passing message from intermediate buffer to target application
• 从buffer取信息处理

System model

• Processes can communicate reliably over one-to-one channels

• Processes may fail only by crashing

• Processes are members of groups, which are the destinations of messages sent with the multicast operation

• Message m:
• Contains ID of sender (sender(m)) and of destination group (group(m))

• Operations
• multicast(g, m) : Multicast message m to group g
• delivery(m) : Delivery of message at recipient

Basic Multicast

• Guaranteed delivery, unless multicasting process crashes

• Primitives and implementation
• Use a reliable one-to-one send() operation
• B-multicast(g, m): for each process , send(p, m)
• B-deliver(m) at : when receive(m) at , for all

• ack-implosion:
• Problem in using concurrent send(p, m) operations
• All recipients acknowledge receipt at about same time
• Buffer overflow leads to dropping of ack messages
• Retransmits, even more ack messages

Reliable Multicast

On initialization 
	Received := {};

For process p to R-multicast message m to group g 
	B-multicast(g,m); (p∈g is included as destination)

On B-deliver(m) at process q with g = group(m) 
	if (m ∉ Received):
		Received := Received ∪ {m};
		if (q ≠ p):
			B-multicast(g,m); 
		R-deliver(m)

• Integrity
• A correct process delivers a message at most once
• A delivered message is identical to the message sent in the multicast send operation
• R-Multicast: Based on underlying communication medium

• Validity
• If a correct process multicasts message m, then it will eventually deliver m (liveness)
• R-Multicast: A correct process will eventually B-deliver to itself

• Agreement
• If a correct process delivers a message m, then all other correct processes in the target group of message m will also deliver message m
• R-Multicast: B-multicast to all other processes after B-deliver

• Validity and agreement ensure overall liveness
• If one process delivers a message m, then m will eventually be delivered to all group members

• Inefficient
• Each message is sent times to each process

Ordered Multicast

FIFO Multicast

• If a correct process issues a multicast(g, m) and then multicast(g, m’), then every correct process that delivers m’ will deliver m before m’

• Use sequence numbers and delay delivery until agreement in sequence numbers between sender and receiver is reached

• Each process p maintains the following sequence numbers:

• : # of messages sent by p to g

• : # of messages delivered at p from q, for each process q != p

Causal ordering

• If multicast(g, m) → multicast(g, m’), where → is induced by message passing only, then every correct process that delivers m’ will deliver m before m’

• Use vector timestamps (only) for multicast messages

• Each process maintains its own vector timestamp

• : number of messages delivered at from

Total Ordering

• If a correct process delivers m before it delivers m’, then any other correct process that delivers m’ will deliver m before m’

• Use global sequence numbers

Relations

• If Casual Multicast, must be FIFO Multicast, not vice versa.

• Casual Multicast DOESN'T imply TO Multicast, vice versa.