distributed systemsocx


Types of ordering in group communication for distributed systems

A group is an operating system abstraction for a collective of related processes. A set of cooperative processes may, for example, form a group to provide an extendable, efficient, available and reliable service. The group abstraction allows member processes to perform computation on different hosts while providing support for communication and synchronisation between them. A reliable multicast protocol allows a group of processes to agree on a set of messages received by the group. Each message should be received by all members of the group or by none. The following are the different types of ordering:-

Total ordering

This guarantees that all correct processes receive all messages in the same order. That is, if correct processes p and q both receive messages m and m', then p receives m before m' if and only if q receives m before m'. The multicast is atomic across all members of the group. 

Note that this definition of a totally ordered broadcast does not require that messages be delivered in causal order or even fifo order, so it is not stronger than these orderings.

For example, if a process suffers a transient failure during the broadcast of message m, and subsequently broadcasts m', a totally ordered protocol will guarantee only that processes receive m'.

Fifo ordering

A fifo ordered protocol guarantees that messages by the same sender are delivered in the order that they were sent. That is, if a process multicasts a message m before it multicasts a message m', then no correct process receives m' unless it has previously received m. To implement this, messages can be assigned sequence numbers which define an ordering on messages from a single source. Some applications may require the context of previously multicast messages from an originator before interpreting the originator's latest message correctly.

However, the content of message m may also depend on messages that the sender of m received from other sources before sending m. The application may require that the context which could have caused or affected the content of m be delivered at all destinations of m, before m. For example, in a network news application, user a broadcasts an article. User b at a different site receives the article and broadcasts a response. User c can only interpret the response if the original article is delivered first at their site.

Casual ordering

Causal order is a strengthening of FIFO ordering which ensures that a message is not delivered until all messages it depends on have been delivered. 

This causal dependence relation is more formally specified as follows:- an execution of a multicast or receive primitive by a process is called an event.

Event e causally precedes event f (i.e. Happened before), (ef), if an only if:

1. A process executes both e and f in that order, or

2. E is the multicast of message m and f is the receipt of m, or

3. There is an event h, such that eh and hf.

A causal protocol then guarantees that if the broadcast of message m causally precedes the broadcast of m', then no correct process receives m' unless it has previously received m.

The definition of causal ordering does not determine the delivery order of messages which are not causally related. Consider a replicated database application with two copies of a bank account x residing at different sites. A client side process at one site sends a multicast to the database to lodge £100 to account x. At another site simultaneously, a client side process initiates a multicast to add 10% interest to the current balance of x. For consistency, all database replicas should apply the two updates in the same sequence. As these two messages are not causally related, a causal broadcast would allow the update messages to x to be delivered in different sequences at the replicas.