---
title: "Reliable multicast properties, algorithm"
subject: "Distributed System"
chapter: 6
key: "semester_7/distributed_system:reliable-multicast"
source: https://www.bctengineer.com/q/semester_7/distributed_system/reliable-multicast
site: BCT Engineering
---

# Reliable multicast properties, algorithm

Distributed System · Chapter 6: Coordination and Agreement

- Asked in: 2076 Asoj
- Video: [Distributed Systems 4.2: Broadcast ordering](https://www.youtube.com/watch?v=A8oamrHf_cQ) — Martin Kleppmann
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/reliable-multicast
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6

## Question

Explain reliable multicast with its properties and an algorithm.

## Short answer

Reliable multicast guarantees delivery to all correct group members or none, despite message loss. Properties: integrity, validity, agreement. One algorithm uses basic multicast with sequence numbers, piggybacked ACKs, NACKs for missing messages, and retransmission.

## Answer

**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)
```text
 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the agreement property of reliable multicast say?
   A. If a correct process delivers m, all other correct processes eventually deliver m
   B. A process delivers m twice
   C. Messages are delivered in FIFO order
   D. The sender must never fail
   Answer: A. Agreement ensures all-or-none delivery among correct members. (Key point: Agreement property)

2. In the acknowledgement-based algorithm, what does q do on receiving a message with S > R+1?
   A. Delivers it immediately
   B. Holds it in a queue and sends a NACK for the missing messages
   C. Discards it as a duplicate
   D. Re-multicasts it to the group
   Answer: B. A gap means earlier messages were lost, so it is held back and retransmission is requested. (Key point: Sequence numbers)

3. In the eager algorithm over reliable channels, why does each process re-multicast on first receipt?
   A. To check order
   B. To reduce messages
   C. So if the sender crashes after reaching one correct process, all correct processes still get the message
   D. To detect duplicates only
   Answer: C. Redundant forwarding gives agreement at the cost of O(N^2) messages. (Key point: Eager algorithm)

## Related in other subjects

- [Random number properties; KS test algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-properties-ks-algorithm) — Simulation and Modeling, chapter 6
- [Recursion properties, Fibonacci, TOH algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-properties-fibonacci-toh) — Data Structure and Algorithm, chapter 5
- [Random number properties and Gap test](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-properties-gap-test) — Simulation and Modeling, chapter 6, asked 4×
- [B-tree properties; order 5 for 3, 14, 7, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-properties-order5-3-14) — Data Structure and Algorithm, chapter 6, asked 2×