Ordered and reliable multicast communication
Ordered and reliable multicast communication
复制标题
DOI：
10.1145/128738.128741
复制
发表时间：
1991-08
期刊：
影响因子：
--
通讯作者：
H. Garcia-Molina;Annemarie Spauster
中科院分区：
文献类型：
--
作者：
H. Garcia-Molina;Annemarie Spauster
组播(向网络中的站点子集发送消息)已成为分布式系统中流行的进程间通信机制。许多应用程序(例如，分布式数据库)要求将消息传输到多个进程。任何类型的消息传输的一个无可争辩的合乎要求的质量是可靠性。从进程A发送到进程B的消息应该确实会到达。更好的是，它应该在合理的时间内到达。对于分布式应用程序，通常还希望多目标消息以一致的顺序到达目标进程。在数据库应用程序中，如果更新请求发送到两个带有数据副本的目的地，则在两个目的地以相同的顺序传递请求有助于保持一致性。这只是一致的消息传递如何简化分布式应用程序的一个例子。在本论文中，我们考虑通过提供有序性和可靠性来增强组播通信。我们提出了一种算法，即传播图算法，它保证了一个强序性质：多组排序。传播图技术的实验分析表明，与其他解决方案相比，该技术是有效的，并且具有明显的负载/延迟折衷。我们还给出了多播排序算法可以提供的几种类型的可靠性。我们讨论了如何使用传播图算法来实现这些类型的可靠性。此外，我们通过给出消息排序的形式化模型和可靠性属性的形式化定义来阐明可靠性问题。然后将这些属性应用于传播图解。
Multicasting (sending a message to a subset of sites in a network) has become a popular mechanism of 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.