The Use of Efficient Broadcast Protocols in Asynchronous Distributed Systems
The Use of Efficient Broadcast Protocols in Asynchronous Distributed Systems
复制标题
高效广播协议在异步分布式系统中的使用
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
Frank B. Schmuck
中科院分区：
文献类型：
--
作者：
Frank B. Schmuck
可靠的广播协议是分布式和容错编程的重要工具。它们对于共享信息和维护分布式系统中的复制数据非常有用。然而，已经提出了广泛的此类协议。这些协议的不同之处在于它们的容错性和交付顺序特征。在广播协议的成本和它提供的排序量之间存在权衡。因此，只要可能，最好采用只支持低程度排序的协议。本文提出了一种技术，用于决定一个协议在解决给定的应用问题时需要多强有序。我们展示了两类不同的应用程序问题：可以用高效的异步协议解决的问题，以及需要全局排序的问题。我们引入线性化函数的概念，将部分有序的事件集映射到完全有序的历史。我们将展示如何构造一个异步实现，在找到线性化函数的情况下解决给定问题。我们证明，一般来说，问题是否具有异步解决方案的问题是不可确定的。因此，对于给定的问题，不存在能够自动构造合适的线性化函数的通用算法。因此，我们考虑一类具有交换性性质的重要问题。我们介绍了为该类构造异步实现的技术。这些技术对于为广泛的实际问题构建高效的异步实现非常有用。
Reliable broadcast protocols are important tools in distributed and fault-tolerant programming. They are useful for sharing information and for maintaining replicated data in a distributed system. However, a wide range of such protocols has been proposed. These protocols differ in their fault tolerance and delivery ordering characteristics. There is a tradeoff between the cost of a broadcast protocol and how much ordering it provides. It is, therefore, desirable to employ protocols that support only a low degree of ordering whenever possible. This dissertation presents techniques for deciding how strongly ordered a protocol is necessary to solve a given application problem. We show that there are two distinct classes of application problems: problems that can be solved with efficient, asynchronous protocols, and problems that require global ordering. We introduce the concept of a linearization function that maps partially ordered sets of events to totally ordered histories. We show how to construct an asynchronous implementation that solves a given problem if a linearization function for it can be found. We prove that in general the question of whether a problem has an asynchronous solution is undecidable. Hence there exists no general algorithm that would automatically construct a suitable linearization function for a given problem. Therefore, we consider an important subclass of problems that have certain commutativity properties. We present techniques for constructing asynchronous implementations for this class. These techniques are useful for constructing efficient asynchronous implementations for a broad range of practical problems.