-
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).
-
Unanimous Update
An update must succeed on all copies or none. A read can succeed from
any one copy. Writes use 2 phase commit.
-
Available Copy
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
Voting algorithms include a mechanism for deciding if enough copies of
a file are available to proceed with updates safely.
-
Majority Voting
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
version.
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).
-
Weighted Voting
The availability of the replicated file may be tuned, to deal with
different kinds of failures, by associating weights with votes at
particular sites.
-
Quorum Consensus
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
consensus voting.
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
finishing.