Darrell Long

Darrell Long

Optimistic Algorithms for Replicated Data Management


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 insure a consistent view of the data so that it appears as though there were only a single replica of the data. The view presented to the user must remain consistent even in the presence of site failures and network partitions.

The simplest consensus algorithm is static majority consensus voting. Static majority consensus voting provides consistency control and mutual exclusion, but does not provide the highest possible availability of data since it requires that a majority of the sites to be reachable for an access request to be granted.

An attempt to remedy the short-comings of static majority consensus voting, known as dynamic voting, was introduced by Davcev and Burkhard. Their algorithm improved the performance by allowing quorums to be adjusted automatically during system operation. The method that we propose, called Optimistic Dynamic Voting, operates on possibly out-of-date information, hoping for the best. It can be shown that the scheme provides mutual exclusion and that data consistency is preserved. There are many benefits to our scheme, including efficiency and ease of implementation.


  author       = {Darrell D. E. Long},
  title        = {Optimistic Algorithms for Replicated Data Management},
  booktitle    = {Proceedings of the Second Workshop on Large-Grained Parallelism},
  month        = nov,
  year         = {1987}

Read full paper here.