Replicating a data object improves the availability of the data, and can improve access latency by locating copies of the object near to their use. When accessing replicated objects across an internetwork, the time to access different replicas is non-uniform. Further, the probability that a particular replica is inaccessible is much higher in an internetwork than in a local-area network (LAN) because of partitions and the many intermediate hosts and networks that can fail. We report three replica-accessing algorithms which can be tuned to minimize either access latency or the number of messages sent. These algorithms assume only an unreliable datagram mechanism for communicating with replicas. Our work extends previous investigations into the performance of replication algorithms by assuming unreliable communication. We have investigated the performance of these algorithms by measuring the communication behavior of the Internet, and by building discrete-event simulations based on our measurements. We find that almost all message failures are either transient or due to long-term host failure, so that retrying messages a few times adds only a small amount to the overall message traffic while improving both access latency as long as the probability of message failure is small. Moreover, the algorithms which retry messages on failure provide significantly improved availability over those which do not.

Many wide-area distributed applications, including distributed databases, can be implemented using a group communication mechanism. We have developed a family of weak-consistency group communication mechanisms, based on the timestamped anti-entropy communication protocol, that provides the scalability and fault-tolerance needed by wide-area systems. We discuss an object-oriented framework for constructing this kind of group communication mechanism, and how its components can be selected to take advantage of specific application semantics. We examine several design choices that we made in building two very different wide-area distributed database applications, and how this framework led to simple, efficient implementations in both systems.

Refdbms is a database system for sharing bibliographic references among many users at sites on a wide-area network such as the Internet. This paper describes our experiences in building and using refdbms for the last two years. It summarizes the collection of facilities that refdbms provides, and gives detailed information on how well refdbms functions as a collaborative, wide-area, distributed information system.