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.
- 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.