Abstract: Performance of Mobile, Single-Object, Replication Protocols
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.