For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.
Broadcast mechanisms of various sorts are ways to ensure that a process can send a message to all other processes in a message-passing system, with various consistency guarantees depending on the needs of the application (for more details, see AttiyaWelch Chapter 8). The interface is similar to that for message-passing; a process initiates a broadcast with a broadcast-send event, and the messages are delivered with broadcast-receive events. The underlying broadcast mechanism translates these events into sequences of send and receive operations.
The minimal guarantee for broadcast is similar to that for message-passing: no message is received unless previously sent, and (in the absence of failures) every message sent is eventually received by all processes.
By providing additional guarantees, we can use broadcast mechanisms to reduce the confusion of an asynchronous system. These additional guarantees take the form of ordering guarantees or reliability guarantees.
1. Ordering guarantees
These control in what order broadcasts are received. They are an attempt to constrain some of the confusion that otherwise arises in an asynchronous system. The motivation is similar to that for Synchronizers, but here we do not insist on simulating a fully synchronous execution, allowing for an implementation that is both cheaper and puts fewer constraints on the algorithm that uses it.
These three guarantees are all described in more detail in AttiyaWelch §8.1.2.1:
- Single-source FIFO
If some single process sends message m1 and m2, then no process receives m2 before m1. Trivially obtained by assuming FIFO channels or by tagging each broadcast with a sequence number, and delaying any received messages that are out of order.
- Totally ordered
If any process receives m1 before m2 (no matter who sends them), then no process receives m2 before m1. Does not imply single-source FIFO: it's still totally ordered if somebody's messages get delivered in a different order from how they were sent, as long as they are delivered in the same different order to all processes.
- Causally ordered
If broadcast-send(m1) ⇒S broadcast-send(m2), then no process receives m2 before m1. Implies single-source FIFO but not total ordering.
Note that we don't say that all processes receive m1 before m2, because it is possible that some processes don't receive either message at all (e.g., in a system with failures and crummy reliability guarantees). The ordering constraint only comes into play if both messages are received.
Single source FIFO broadcast is mostly useful for implementing totally-ordered broadcast. Totally-ordered broadcast is mostly useful for implementing causally-ordered broadcast. Causally-ordered broadcast is useful for implementing replicated state machines: to execute an operation, I broadcast it, and then each replica applies the operation when it receives it.
2. Reliability guarantees
- Integrity
- Every message received was previously sent.
- No duplicates
- No message is delivered more than once.
- Nonfaulty liveness
- Every message that is sent by a nonfaulty is eventually delivered to all nonfaulty processes.
- Faulty liveness
- Every message that is delivered to at least one nonfaulty process is eventually delivered to all nonfaulty processes. (This includes messages sent by faulty processes.)
A broadcast mechanism that satisfies all of these constraints is called reliable.
Integrity and no duplicates are usually provided by the underlying point-to-point message-passing mechanism (and if not, can be implemented as if they were). The other properties are trickier, and depend on the implementation of the broadcast primitive.
3. More jargon
- Atomic broadcast
- Totally-ordered + reliable.
- FIFO atomic broadcast
- Single-source FIFO + reliable.
- Causal atomic broadcast
- Causally-ordered + atomic broadcast. Basically satisfies everything.
Note that atomic broadcast is sufficient to implement AsynchronousConsensus (broadcast your input, agree on the first value delivered). So there is no implementation of atomic broadcast in a system with at least one failure without assuming extra mechanisms, e.g. FailureDetectors or randomization.
Basic reliable broadcast (with no ordering guarantees) and FIFO atomic broadcast can both be implemented by having nonfaulty recipients rebroadcast any messages they receive; see ReliableBroadcast.
4. Implementing totally-ordered broadcast
Here is a trivial algorithm (see also AttiyaWelch §8.2.3.1). A single coordinator process p collects messages to be broadcast using standard point-to-point messages, and then broadcasts them using single-source FIFO broadcast.
For this algorithm, total ordering follows immediately from FIFO ordering on broadcasts by the coordinator. If we assume the messages to the coordinate travel along FIFO point-to-point channels, we also get single-source FIFO for each process. In general we do not get causal ordering unless the only communication is by broadcast: if p1 sends a broadcast to the coordinate and then a message to p2, and p2 responds to this message by itself sending a broadcast to the coordinator, then the two broadcasts are causally related by there is no guarantee which arrives at the coordinator first. On the other hand, if the only way that p1 and p2 communicate is through broadcasts, then any broadcast of p1 that happens-before some broadcast of p2 must be connected by a chain of intermediate broadcasts that left the coordinator before p2's broadcast arrived; so in this case we do get causal ordering.
A slightly less trivial algorithm avoids this problem by ordering messages using timestamps, similar a logical clock (see LogicalClocks; the mechanism is also similar to the multi-writer version of ABD shared memory simulation described in MessagePassingVsSharedMemory). Each process keeps a vector of the last timestamp received from each process (including itself). To initiate a broadcast, a process chooses a new timestamp greater than the max of all previous timestamp, and appends its own id to the end to break ties. It then issues a single-source FIFO broadcast. Each process that receives the message holds it until it knows that no message with a lower timestamp is in transit; specifically, until its timestamp field for every other process is at least as large as the message's timestamp. To prevent deadlock, if the timestamp on an incoming message is greater than the receiver's own timestamp, it increases its own timestamp to the one it received and single-source FIFO broadcasts a message timestamp-update(new timestamp) to let everybody else know it will not be sending any lower-timestamp messages.
This provides total ordering. The proof is that all process deliver messages in order of increasing timestamps (because I can't receive a broadcast with a low timestamp from some process after I receive a broadcast or a timestamp-update message with a higher timestamp due to the single-source FIFO property). If we tack timestamps onto all messages (not just broadcasts) and update them as in LogicalClocks, it also provides causal ordering, since if broadcast-send(m1) ⇒ broadcast-send(m2), there must be some chain of messages that carries m1's timestamp to m2's sender before m2 is sent.