The Use of Efficient Broadcast Protocols in Asynchronous Distributed Systems
Frank Schmuck · NASA STI Repository (National Aeronautics and Space Administration) · 1988
Reliable broadcast protocols are important tools in distributed and fault-tolerant programming. They are useful for sharing information and for maintaining repli-cated data in a distributed system. However, a wide range of such protocols has been proposed. These protocols Mer 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. JAbAew that there are two distinct classes of application problems: problems I that ca,n be solved with efficient, asynchronous protocols, and problems that require global ordering. Wehtrduce the concept of a Zincarkztion finction that maps par-tially ordered sets of events to totally ordered histony W b how to construct an asynchronous implementation that solves a given problem if a linearization func-