[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.

A reliable broadcast protocol for AsynchronousMessagePassing with crash failures guarantees that if some non-faulty process delivers (to itself) a broadcast message, every non-faulty process delivers it exactly once. See also Broadcast for many more variants of broadcast.

Here's the reliable broadcast protocol used in the Chandra-Toueg consensus protocol (see FailureDetectors). Note that this does not actually depending on having failure detectors and will work in any asynchronous message-passing system with crash failures.

Broadcast
Send msg to all processes.
Upon receiving msg
If this is the first time I saw msg, send msg to all processes, then deliver msg to myself.

It's clear that I deliver the message to myself at most once. If I am non-faulty, then the fact that I am non-faulty means that I successfully send it to everybody else, and that all my non-faulty peers also receive the message at least once and deliver it.


CategoryDistributedComputingNotes


2014-06-17 11:58