Friday, February 19, 2010
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.
Pros
Pros
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),
- Best-effort broadcast
- Reliable broadcast
- Uniform reliable broadcast
- Lazy reliable broadcast
- Eager reliable broadcast
- Causal reliable broadcast
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
- Simpler implementation
- Works if only sender is reliable
Cons
- Sender centric algorithm, so it is not scalable
- 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
- Carries all pros from BEB
- Provides atomicity(either all or none of the correct node delivers)
Cons
- 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 m1 precedes m2 then,Properties
- if m1 and m2 is broadcasted from the same process then m1 broadcasted before m2
- if m1 is delivered by process p then p broadcasted m2 after delivering m1
- 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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment