Broadcast: best-effort, reliable and uniform reliable

Just like the previous post about fairloss, stubborn and reliable channel (here), I want to note down three types of broadcast that are easily confused: best-effort, reliable and uniform reliable.

Let’s assume that the channel we are using for broadcasting is reliable, which mean that the package that is sent will be delivered and no duplication is made, then:

Best effort broadcast says that it will delivered the message being broadcast to every correct node. The term correct node here means that the node does not crash and runs as expected. It also guarantees that there is no duplicate message and no message being delivered with out being sent before. So basically, the best effort broadcast just uses the reliable link for broadcasting without any additional feature. This method has no problem with a perfect network without any node being crashed. However, if the sender crashes, best effort is not able to assure the broadcast.
Reliable broadcast fixes that problem by saying that if just one correct process delivers the message then every one must be delivered. In other words, either no correct one receives or every correct one receives (we don’t care if the crashed ones receive or not). In this broadcast, if the sender crashes in the middle of broadcast and some processes already delivered the message then it makes sure that every other correct processes will deliver also. This is implemented based on the idea that:

  • Checks correctness of every process during the broadcast. If one process crashes, tell the processes that delivered the message from the crashed one to broadcast again.
  • Before delivering one message, check for correctness of sender then decide if one should re-broadcast or not.

The second point is just an optimization, not to wait until the next check to find the crashed process but check right after delivering the message.
Until now, we only talk about correct receivers. What if some of the receivers crash? If we use best-effort or reliable, we just ignore it. But what if one process delivered the message then do some thing and crash? The reliable only assures that if a correct process delivered, now we have a crash process delivered, then it doesn’t make sure that other will also deliver. In order to cover that case, people think of the idea that instead of delivering right away after receiving the message, each process will mark it as ‘received’ and wait until everyone ‘received’ then delivered. That is the idea of uniform reliable broadcast. It says that if one process delivers the message (correct or crash doesn’t matter), every correct one delivers the message.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s