The Use of Efficient Broadcast Protocols in Asynchronous Distributed Systems
Abstract
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 event 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 cons tructing asynchronous implementations for this class.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1988
- Accession Number
- ADA197810
Entities
People
- Frank B. Schmuck
Organizations
- Cornell University