Abstract: Decentralized Replicated-Object Protocols
We describe a new replicated-object protocol designed for use in mobile and
weakly-connected environments. The protocol differs from previous protocols
in combining epidemic information propagation with voting, and in using
fixed per-object currencies for voting. The advantage of epidemic protocols
is that data movement only requires pairwise communication. Hence, there is
no need for a majority quorum to be available and simultaneously connected
at any single time. The protocols increase availability by using voting,
rather than primary copy or primary commit schemes. Finally, the use of
per-object voting currencies allows votes to take place in an entirely
decentralized fashion, without any server having complete knowledge of
group membership.
We show that currency allocation can be used to implement diverse
policies. For example, uniform currency distributions emulate traditional
dynamic voting schemes, while allocating all currency to a single server
emulates a primary-copy scheme. We present simulation results showing both
schemes, as well as the performance advantages of using currency proxies to
temporarily reallocate currency during planned disconnections.