Message ordering in a multicast environment

Three ordering properties are characterized, namely, single-source, multiple-source, and multiple-group ordering, and their solutions are discussed. The multiple-group ordering property, which guarantees that two messages destined to two processes are delivered in the same relative order, even if they originate at different sources and are addressed to different multicast groups, is concentrated on. A protocol that solves the multiple-group ordering problem is presented. The issues of performance and reliability are addressed by providing comparisons with other techniques for ordering multicasts. In many cases this new algorithm solves the problem with greater efficiency than previous solutions without sacrificing reliability. It is pointed out that one disadvantage of the technique is that sometimes sites are required to handle messages which they do not need to deliver locally. These so-called extra nodes, however, do not occur frequently according to the experiments presented