Optimistic Algorithms for Replicated Data Management

Abstract

In a distributed system, data are often replicated for protection against site failures and network partitions. Through the use of replication, increased availability of data and reliability of access can be obtained. When data are replicated at several sites, an access policy must be chosen to ensure a consistent view of the data as though there were only a single replica. The simplest consensus algorithm, static majority consensus voting, provides consistency control and mutual exclusion, but does not achieve the highest possible availability since it requires a majority of sites to be reachable for any access request. We propose Optimistic Dynamic Voting, which operates on possibly out-of-date information about system state. We show that the scheme preserves mutual exclusion and data consistency while offering benefits in efficiency and ease of implementation.