Ordered and Reliable Multicast Communication (Thesis)
Abstract:
Multicasting (sending a message to a subset of sites in a network) has
become a popular mechanism for interprocess communication in
distributed systems. Many applications (e.g., distributed databases)
require that a message be transmitted to multiple processes. One
indisputably desirable quality of any type of message transmission is
reliability. A message that is sent from process A to process B should
indeed arrive. Even better, it should arrive within a reasonable
amount of time. For distributed applications, it is also often
desirable for multidestination messages to arrive at the destination
processes in a consistent order. In a database application, if update
requests are headed to two destinations with copies of the data,
delivering the requests in the same order at both destinations helps
maintain consistency. This is just one example of how consistent
message delivery simplifies distributed applications. In this thesis,
we consider enhancing multicast communication by providing ordering and
reliability properties. We present an algorithm, the propagation graph
algorithm, that guarantees a strong ordering property: multiple group
ordering. Experimental analysis of the propagation graph technique
demonstrates that it is efficient compared to other solutions and
exhibits a clear load/delay tradeoff. We also present several types of
reliability that multicast ordering algorithms can provide. We address
how to achieve these types of reliability with the propagation graph
algorithm. Further, we clarify the issue of reliability by presenting
a formal model of message ordering and by presenting formal definitions
of reliability properties. These properties are then applied to the
propagation graph solution.