06/01/1991 09:00 AM
Computer Engineering
Many wide-area distributed applications use replicated data to improve the availability of the data, and to improve access latency by locating copies of the data near to their use. This paper presents a new family of communication protocols, called *quorum multicasts*, that provide efficient communication services for widely replicated data. Quorum multicasts are similar to ordinary multicasts, which deliver a message to a set of destinations. The new protocols extend this model by allowing delivery to a subset of the destinations, selected according to distance or expected data currency. These protocols provide well-defined failure semantics, and can distinguish between communication failure and replica failure with high probability. We have evaluated their performance, which required taking several traces of the Internet to determine distributions for communication latency and failure. A simulation study of quorum multicasts, based on these measurements, shows that these protocols provide low latency and require few messages. A second study that measured a test application running at several sites confirmed these results.
