Ordered and reliable multicast communication
Héctor García-Molina, Annemarie Spauster · ACM Transactions on Computer Systems · 1991
A mnlticast group is a collection of processesthat are the destinations of the same sequenceof messages.These messagesmay originate at one or more source sites and the destination processesmay run on one or more sites, not necessarily distinct.The nmlticast groups may overlap.A multieast protocol is responsible for the delivery of messagesto the appropriate processes.Someapplications require that the protocol provide someguaranteeson the order in which messagesare delivered.In addition, in many casesreliability of delivery is essential.In this paper we -&rracterize three ordering properties and discusstheir solutions.We concentrate on the multiple group ordering property, which guarantees that two messages destined to two processesare delivered in the samerelative order, even if they originate at different sourcesand are addreseedto different mnlticast groups.We present a new protocol called the propagation graph algorithm that solves the multiple group ordering problem by org-g sites logically into a forest.We present simulation results that illustrate the performance of our algorithm compared to other techniques for ordering multicasts.We address the issue of reliability by considering the various types of reliability a protocol can provide and exploring one of these types of reliability with the propagation graph algorithm.We also consider the reliability of other solutions.In many eases our new algorithm solves the problem with greater efficiency than previous solutions without sacrificing reliability.