Reliable Broadcast

Reliable broadcast is a necessary component for many distributed algorithm. For client server architecture we are lucky that there is TCP :) to support reliable message delivery, which handles packet loss, packet retransmission, duplicate messages etc. But unfortunately distributed architecture is much complex then that, where we have multiple recipients and our target is to scale as the recipients grow.

There are lots of ways to broadcast messages. Each provides some property and cost so that we can pick according to our need.

We can classify reliable broadcast in many categories(in general),

1. Best-effort broadcast
2. Reliable broadcast
3. Uniform reliable broadcast
4. Lazy reliable broadcast
5. Eager reliable broadcast
6. Causal reliable broadcast

Here are the properties, pros and cons of each type,

Best-effort broadcast (BEB)

Properties

BEB1: Validity	If a correct process pi broadcasts a message m, then pi eventually delivers m
BEB2: No duplication	No duplicate message is delivered
BEB3: No creation	No message delivered unless broadcast

Pros

1. Simpler implementation
2. Works if only sender is reliable

Cons

1. Sender centric algorithm, so it is not scalable
2. Does not work if sender crashes

Implementation

Send the message to all the nodes using perfect channel. Perfect channel takes care of the Best-effort-Validity.

Reliable broadcast (RB)

Property

RB1: Validity	BEB1
RB2: No duplication	BEB2
RB3: No creation	BEB3
RB4: Agreement	If a message m is delivered by some correct process pi, then m is eventually delivered by every correct process pj

Pros

1. Carries all pros from BEB
2. Provides atomicity(either all or none of the correct node delivers)

Cons

1. Carries all pros from BEB

Uniform Reliable broadcast (URB)

Property

URB1: Validity	BEB1
URB2: No duplication	BEB2
URB3: No creation	BEB3
URB4: Agreement	If a message m is delivered by any process pi, then m is eventually delivered by every correct process pj

Lazy Reliable Broadcast

Requires: Perfect failure detector

Property

The is a non zero probability if the sender and receiver is correct then eventually the receiver will receive the message.

Basic idea

If any node detects that the sender has crashed then RB deliver a copy of the message to all node.

Eager Reliable Broadcast

Property

Same as Lazy Reliable Broadcast. But it does not use any failure detector. It work is fail silent model

Basic idea

It does not wait for node to crash and does the RB deliver to all node.

Causal reliable broadcast

Till now we did not consider order of the messages. But if the broadcast messages are related and has a order such that m₁ precedes m₂ then,

Properties

1. if m1 and m2 is broadcasted from the same process then m1 broadcasted before m2
2. if m1 is delivered by process p then p broadcasted m2 after delivering m1
3. the precedence is transitive, so if m1 precedes m' and m' precedes m2 then m1 precedes m2

References

• Introduction to Reliable Distributed Programming by Rachid Guerraoui and Luís Rodrigues
• Slides from the lectures of Professor Seif Haridi, SCS/ICT/KTH.