CS505 Broadcast

Network provides one-to-one communication primitives · – Sometimes one-to-many also ·  Membership opaque ·  Fuzzy guarantees · Need one-to-many communication primitives · – E.g., replication, peer discovery · – With reliability guarantees! ·  And possibly ordering · Distributed Systems · Example: Reliable Broadcast · Informally

– A process p1 wants to send a message m to several processes p2…pn

Scenario · – Chat, mailing list, … · Assume · – Asynchronous system · – Reliable channels · – Crash-stop failures of processes · Best-effort Broadcast · Generalized

Any process in a group can broadcast Primitive broadcast (and deliver) behave as follows

I. · II. · III. · Validity · Implementation · – broadcaster sends m to every process including itself · – Every process which receives m delivers m · What if

– p1 sends to p2, and then crashes, or shuts off?

E.g., “hand in solutions for assignment x by …” · Reliable Broadcast · I. · II. · III. · Validity · IV. · Agreement

If one correct process delivers a message m, every correct process eventually delivers m

Proposal

– p sends m to every other process including itself

– Every process which receives m for the first time sends it to every other process (except the sender) and delivers it