Terminating Reliable Broadcast

Terminating Reliable Broadcast (TRB) is a problem in distributed computing that encapsulates the task of broadcasting a message to a set of processes in the presence of faults. In particular, any of the processes, including the sender, might fail ("crash") at any time.

Formal Properties

In general, a TRB protocol must satisfy four properties, below. A process is called "correct" if it does not fail at any point during its execution. A special message, $\mathrm {SF}$ ("sender faulty"), can be delivered if the sender fails.

• Termination: every correct process delivers some value.
• Validity: if the sender is correct and broadcasts a message $m$, then every correct process should deliver $m$.
• Integrity: a process delivers a message at most once, and if it delivers some message $m\neq \mathrm {SF}$, then $m$ was broadcast by the sender.
• Agreement: if a correct process delivers a message $m$, then all correct processes deliver $m$.