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

Problem description

A TRB protocol typically organizes the system into a sending process and a set of receiving processes, which may include the sender itself. A process is called "correct" if it does not fail at any point during its execution. The goal of the protocol is to transfer data (the "message") from the sender to the set of receiving processes. A process may perform many I/O operations during protocol execution, but eventually "delivers" a message by passing it to the application on that process that invoked the TRB protocol.

("sender faulty"), if the sender failed, but either all or none will. A correct process is therefore guaranteed that data delivered to it was also delivered to all other correct processes.

More precisely, a TRB protocol must satisfy the four formal properties below.

• Termination: every correct process delivers some value.

• Validity.

• Integrity was broadcast by the sender.

• Agreement.

The presence of faults in the system makes these properties more difficult to satisfy. A simple but invalid TRB protocol might have the sender broadcast the message to all processes, and have receiving processes deliver the message as soon as it is received. This protocol, however, does not satisfy agreement.

TRB is closely related, but not identical, to the fundamental distributed computing problem of consensus.

References