Performance of Mobile, Single-Object, Replication Protocols

In The 19th Symposium on Reliable Distributed Systems (SRDS), October 2000.

Ugur Cetintemel and Pete Keleher

This paper describes bounded voting: a new replicated-object protocol designed for use in mobile and weakly-connected environments. We show that the protocol eliminates several restrictions of previous work, such as the need for (1) strong or complete connectivity, (2) complete knowledge of system membership, and (3) low update rates. The protocol primarily differs from previous work in implementing a novel, asynchronous, weighted-voting scheme via epidemic information flow, and in committing updates in an entirely decentralized fashion, without requiring any server to have complete knowledge of system membership. Since only pairwise communication is required, there is no need for a majority quorum to be available and simultaneously connected at any single time. A proxy mechanism is used to enable transparent handling of planned disconnections, a failure mode unique to mobile systems.

We use a detailed simulation study to characterize the performance of bounded voting under a variety of loads and environment, and to compare it to another pessimistic epidemic protocol. We further describe the performance impact of extending the basic protocol to incorporate transparent proxies for planned disconnections.

	title = "Performance of Mobile, Single-Object, Replication Protocols",
	author = "Ugur Cetintemel and Pete Keleher",
	booktitle = {The 19th Symposium on Reliable Distributed Systems (SRDS)},
	month = {October},
	year = {2000},

Available: bibtex, abstract,