Group Communication

The following are the three main types or orderings that have been studied in the context
of ordered multicasts:

    1. Local order multicast (also called single-source FIFO)
    2. Causal order multicast
    3. Total order multicast

Local order multicast: In local order multicast, if a process multicasts two messages in the
order (m1, m2), then every correct process in the group must deliver m1 before m2. There
are many applications of local order multicast: One is in the implementation of a DSM
where the primary copy of each variable is maintained by an exclusive process, and all
other processes use cached copies of it. Whenever the primary copy is updated, the owner
of the primary copy multicasts the updates to the holders of the cached copies, and these
copies are updated in the same order. Other applications include video distribution and
software distribution.

Causal order multicast: Let m1 and m2 be a pair of messages in a group, such that
sent(m1) ≺ sent(m2). Then causal order multicast requires that every process in the system
must deliver m1 before m2. Local order multicast trivially satisfies this. Causal order multicast
modifies it by imposing delivery orders among causally ordered messages from distinct senders too. Here is an example: A group of students scattered across a large campus are preparing for an upcoming quiz through a shared bulletin board. Someone comes up with a question and throws it to the entire group, and whoever knows the answer multicasts
it to the entire group. The delivery of a question to each student must happen before
the delivery of the corresponding answer, since these are causally related. It will be awkward
(and a violation of the rules of causal ordered multicast) if some student receives the
answer first and then the corresponding question!

Total order multicast: In total order atomic multicast, every member of the group is required
to deliver all messages sent within the group in identical order. It implies that if every process
i maintains a queue Q · i (initially empty) to which a message is appended as soon as it
is delivered, then eventually, for any two distinct processes i and j, Q . i = Q . j. Note that the
order in which the messages are delivered has no connection with the real time at which
these messages were sent out.

MySQL used Total Order multicast for group communication of group replication.