What is a genuine atomic multicast? What is the difference between a genuine and non-genuine atomic multicast?


Atomic multicast is a generalisation of atomic broadcast. In atomic multicast, there are $M \geq 1$ groups of processes $\Gamma = \{ G_1, G_2, \dots, G_M \}$, where $G_i$ is a non-empty group. The groups are usually defined to be non-overlapping or disjoint, that is, groups do not have processes in common. A message $m$ can be sent to one or more groups. The destination groups of a message $m$ are usually defined to be the groups inside the set $m.dst$, that is, m will be delivered by all processes inside the groups which are inside the set $m.dst$. Atomic broadcast is a special case of atomic multicast, where there is only one group which contains all processes.

To be more precise, let us more formally define the atomic multicast (AM) problem. An AM is a reliable multicast, which also requires a "total order" property to be satisfied. Let us first defined a reliable multicast.

A reliable multicast (RM) is defined in terms of two primitive operations, often denoted by R-multicast(m, m.dst) and R-deliver, where $m.dst$ is the set of groups to which $m$ is multicast. R-multicast is used to reliably multicast, that is, to send message $m$ to the groups in $m.dst$, and R-deliver is used to reliably deliver the message $m$ once it has been received by those same groups.

These primitive operations, R-multicast and R-deliver, and, in general, any algorithm which implements RM must satisfy 3 properties:

  1. Validity: If a correct process multicasts $m$, then all correct processes that belong to a group of $m.dst$ deliver $m$

  2. Uniform Agreement: If a process delivers a message m, then all correct processes that belong to a group of $m.dst$ deliver $m$

  3. Uniform Integrity: A process $p$ delivers a message $m$ at most once and only if the group of $p$ is in $m.dst$ and some process has previously multicast $m$.

In addition to these 3 properties, the atomic multicast problem also requires the following property to be satisfied

  1. Local total order: If processes $p$ and $q$ both deliver messages $m$ and $m'$ and $m.dst = {m'}.dst$, then $p$ delivers $m$ before $m'$ if and only if $q$ delivers $m$ before $m'$.

In other words, if the destination groups of the messages $m$ and $m'$ are the same and there are two processes which deliver both $m$ and $m'$, then they must deliver these messages in the same order (or in "total order").

In reality, there are other "total order" properties: for example, there is the "global total order" property. An atomic multicast problem defined in terms of the "global total order" property is different than the atomic multicast problem defined in terms of the "local total order" property. See section 2.2 of the paper "Fault-tolerant Genuine Atomic Multicast" by Carole Delporte-Gallet and Hugues Fauconnier for more details.

I stated that an atomic multicast is a generalization of an atomic broadcast. However, an atomic broadcast can actually be used to implement an atomic multicast. More specifically, to do that, we can atomically broadcast the messages and then only the groups inside $m.dst$ would atomically deliver $m$. However, this would send $m$ to all groups in the system, even though they may not be in $m.dst$. In other words, if we implemented an atomic multicast using the modified version of the atomic broadcast algorithm just explained, all groups and processes in the system would be involved. This implementation would be as costly as the implementation of an atomic broadcast algorithm. We want to avoid this!

A genuine atomic multicast algorithm is an algorithm which solves the atomic multicast problem where only the sender of the message $m$ and the processes in destination groups ($m.dst$) are "concerned" by (or involved in) the atomic multicast of the message $m$.

Thus the adjective "genuine" is associated with the algorithms which solve the atomic multicast problem and not with the problem itself.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.