Basic update algorithms
The following two algorithms show the basic idea of replicated files.
They fail to provide availability in the face of network partitioning
(a common failure mode in large distributed systems).
An update must succeed on all copies or none. A read can succeed from
any one copy. Writes use 2 phase commit.
Updates succeed on all available copies. If a server is down, it is
excluded as a copy. The problem is the difference between detecting a
server down and not reachable.
Voting algorithms include a mechanism for deciding if enough copies of
a file are available to proceed with updates safely.
This scheme simply assigns votes to each copy, together with version
numbers. Rads now use two phases. A first phase collects the latest
versions' votes. The second commits to the read on the latest
Writes collect votes and request to write on all versions. Whenn a
majority of votes is read, the write can be committed (otherwise it
is rolled back).
The availability of the replicated file may be tuned, to deal with
different kinds of failures, by associating weights with votes at
In general, objects are often complex, with different operations
affecting the state of the object differently. This can be exploited
by generalising the idea of weighted votes on copies to quorum
In this scheme, an object's state is represented as a sequence of
timestamped operations on the state. Depending on the semantics of
each operation (read versus write), we can adjust the availability versus
cost by setting a quorum for starting each operation and another for