Terminating Reliable Broadcast
Encyclopedia
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.
operations during protocol execution, but eventually "delivers" a message by passing it to the application on that process that invoked the TRB protocol.
The protocol must provide important guarantees to the receiving processes. All correct receiving processes, for example, must deliver the sender's message if the sender is also correct. A receiving process may deliver a special message,
("sender faulty"), if the sender failed, but either all correct processes will deliver 
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.
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 if faults can occur: if the sender crashes after sending the message to some processes, but before sending it to others, then the first set of processes may deliver the message while the second set delivers
.
.
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
that encapsulates the task of broadcasting a message to a set of receiving processes
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
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/OInput/output
In computing, input/output, or I/O, refers to the communication between an information processing system , and the outside world, possibly a human, or another information processing system. Inputs are the signals or data received by the system, and outputs are the signals or data sent from it...
operations during protocol execution, but eventually "delivers" a message by passing it to the application on that process that invoked the TRB protocol.
The protocol must provide important guarantees to the receiving processes. All correct receiving processes, for example, must deliver the sender's message if the sender is also correct. A receiving process may deliver a special message,
("sender faulty"), if the sender failed, but either all correct processes will deliver 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: if the sender is correct and broadcasts a message
, then every correct process delivers 
. - Integrity: a process delivers a message at most once, and if it delivers some message
, then 
was broadcast by the sender. - Agreement: if a correct process delivers a message
, then all correct processes deliver 
.
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 if faults can occur: if the sender crashes after sending the message to some processes, but before sending it to others, then the first set of processes may deliver the message while the second set delivers
.Context in Distributed Computing
TRB is closely related, but not identical, to the fundamental distributed computing problem of ConsensusConsensus (computer science)
Consensus is a problem in distributed computing that encapsulates the task of group agreement in the presence of faults.In particular, any process in the group may fail at any time. Consensus is fundamental to core techniques in fault tolerance, such as state machine replication.- Problem...
.