SKR 5302: Advanced Distributed Computing

6. Chapter 6: Coordination and Agreement

System model:

Contains a collection of processes, which can communicate reliably over one-to-one channels.
Processes may fail only by crashing.
The processes are members of groups.
To simplify, processes is member of at most one group at a time.
Operation multicast(g, m) sends the message m to all members of the group g of processes.
Operation deliver(m) that delivers a message sent by multicast to the calling process.
Every message m carries the unique identifier of the process sender(m) that sent it and the unique destination group identifier group(m).
Assume that processes do not lie about the origin or destinations of messages.

Basic multicast

A correct process will eventually deliver the message, as long as the multicaster does not crash.
Straightforward way to implement B-multicast is to use a reliable one-to-one send operation:

To B-multicast(g, m): for each process p ∈ g, send(p, m);

On receive(m) at p: B-deliver(m) at p.

Reliable multicast

All correct processes in the group must receive a message if any of them does.
Integrity: A correct process p delivers a message m at most once.
Validity: If a correct process multicasts m, then it will eventually deliver m.
Agreement: If a correct process delivers message m, then all other correct processes in group(m) will eventually deliver m.
If a process that multicasts a message crashes before it has delivered it, then it is possible that the message will not be delivered to any process in the group; but if it is delivered to some correct process, then all other correct processes will deliver it.

Figure 6.9: Reliable multicast algorithm
The algorithm satisfies the validity property, since a correct process will eventually B-deliver the message to itself.
By the integrity property of the underlying communication channels used in B-multicast, the algorithm also satisfies the integrity property.
Agreement follows from the fact that every process B-multicasts the message to the other processes after it has B-delivered it.
If a process does not R-deliver the message, then this can only be because it never B-delivered it.

That in turn can only be because no other correct process B-delivered it either; therefore none will R-deliver it.

Uniform properties

The agreement above refers only to the behaviour of correct processes – processes that never fail.
If a process was not correct and crashed after it had R-delivered a message, since any process that R-delivers the message must first B-multicast it, it follows that all correct processes will still eventually deliver the message.
Uniform agreement: If a process, whether it is correct or fails, delivers message m, then all correct processes in group(m) will eventually deliver m.
It is useful in applications where a process may take an action that produces an observable inconsistency before it crashes.

Ordered multicast

The basic multicast algorithm delivers messages to processes in an arbitrary order, due to arbitrary delays in the underlying one-to-one send operations.
To simplify, the orderings assume that any process belongs to at most one group only.
Common ordering requirements:
- FIFO ordering: If a correct process issues multicast(g, m) and then multicast(g, m’), then every correct process that delivers m’ will deliver m before m’.
- Causal ordering: If multicast(g, m) -> multicast(g, m’), where -> is the happened-before relation induced only by messages sent between the members of g, then any correct process that delivers m’ will deliver m before m’.
- Total ordering: If a correct process delivers message m before it delivers m’, then any other correct process that delivers m’ will deliver m before m’.
The definitions of ordered multicast do not assume or imply reliability.

Figure 6.11: Total, FIFO and causal ordering of multicast messages

Overlapping groups

The preceding definitions considered only non-overlapping groups.
Global FIFO ordering: If a process issues multicast(g, m) and then multicast(g’, m’), then every correct process in g ∩ g’ that delivers m’ will deliver m before m’.
Global causal ordering: If multicast(g, m) -> multicast(g’, m’), where -> is the happened before relation induced by any chain of multicast messages, then any correct process in g ∩ g’ that delivers m’ will deliver m before m’.
Pairwise total ordering: If a correct process delivers message m sent to g before it delivers m’ sent to g’, then any other correct process in g ∩ g’ that delivers m’ will deliver m before m’.
Global total ordering: Let ‘<‘ be the relation of ordering between delivery events. We require that ‘<‘ obeys pairwise total ordering and that it is acyclic.