Reliable Multicast

Question 1

Why is multicast used for group communication?

Answer 1

Its more efficent and transparent to the sender.

Question 2

Why is multicast unreliable? (3)

Answer 2

Multicast doesn’t tolerate process failure.
Omission failures
No guarentees on message order

Question 3

What are the types of group communication?

Answer 3

Closed - Doesn’t change its size
Open - Can change size
Peer to peer - No hierarchy
Hierarchical - 1 higher node.

Question 4

Why is the key property of Reliable Multicast?

Answer 4

All processes in g must receive copies of messages to sent to g.

Question 5

What are the assumptions of Reliable Multicast?

Answer 5

Membership of group is known.
Reliable one-to-one communication.
Only crash failures occur.

Question 6

What are the guarentees of Basic Multicast? (2)

Answer 6

Correct processes will eventually deliver message as long as multicaster doesn’t crash.
Only group members receive messages sent to group.

Question 7

What is an atomic multicast? (2)

Answer 7

Messages are eithe received by all, or none.

Basic reuqirement for group-oriented activties.

Question 8

What are the delivery guarentees of Reliable Multicast? (3)

Answer 8

Integrity: Current process delivers message at most once.
Validity: If Pi multicasts m, Pi delivers m.
Agreement: If Pi delivers m, all other processes will eventually deliver m.

Question 9

What is the process of Basic Reliable Multicast? (3)

Answer 9

Pi multicasts m to g (including to itself).

When a process Pj receives m for the first time, not from sender, it B-multicasts to g and R-delivers m.

Question 10

What is the problem with Basic Reliable Multicast?

Answer 10

It is inefficient.

Question 11

What is the correctness of Reliable Multicast?

Answer 11

Integrity: Yes (duplicates detected)
Validity: Yes ( sender multicasts to itself, so will eventually deliver to itself)
Agreement: If sender R-delivers, then all must have R-delivered.

Question 12

What are the 3 orderings of Multicast?

Answer 12

FIFO, Casual, Total

Question 13

What does casual ordering imply?

Answer 13

FIFO ordering

Question 14

What is the implementation of FIFO ordering? (4)

Answer 14

Each process assigns sequence number to messages sent to g.
Processes remember latest message sent to g.
Messages are queued for delivery until all messages with a lower sequence number have been delivered.

Question 15

What is the issue with a sequencer?

Answer 15

Can cause a bottleneck

Question 16

What are the two phases of the Distributed Agreement?

Answer 16

1 : Pi multicasts timestamped message (m,t) and receives timestamped replies (m,t’).
2 : After Pi receives all responses, Pi multicasts commit message with the largest t’ value as the timestamp.

Question 17

What is the implementation of the Casual Ordering Multicast?

Answer 17

Initialise vector timestamp TS.
For a new message, increment TS.
When receiving a message from Pj:
Place in queue.
Check if all previous messages from Pj have been delivered by Pi.
Check if all previous messages that Pj has delivered have been delivered.
B-deliver m.

Question 18

When are vectortimestamps updated? (2)

Answer 18

Increment own on multicast.

Update others on delivery of message.