Register Client
R0, R3, . . . C0
R1, R4, . . . C1
R2, R5, . . . C2
Figure 4: Sample round r ob in allocation of register sets to clients.
can decide upon different values. Rule 3 (current decision) ensures that all decisions made by a
register set will be for the same value whilst Rule 4 (previous decisions) ensures that all decisions
made by different register sets are for the same value.
3.2 Implementing the correctness rules
Rules 1 and 2 are easy to implement, bu t Rules 3 and 4 requir e more careful treatment.
Rule 3 (current decision). The simplest implementation of Rule 3 is to permit only configura-
tions with one quorum per register set, as in Figure 1b. We generalise this to intersecting quorums
configurations by perm itting multiple quorums per register set, provided that all quorums f or a
given register set intersect, as in Figure 1d. The requirement for intersection ensures that if mul-
tiple quorums in a register set decide a value then they mus t decide the same value as they must
share a common register.
Alternatively, we can support disjoint quorums if we require that all values written to a given
register set are the same. This can be achieved by assigning register sets to clients and requiring
that clients write only to their ow n register sets, with at most one value. In practice, this could
be implemented by using an allo cation such as th at in Figure 4 and by requiring clients to keep a
persistent record of which register sets they have written too. We refer to these as client restricted
configurations.
Both techniques, intersecting quorums configurations and client restricted configurations, can
be combined on a per-register-set basis.
Rule 4 (previous decisions) . Rule 4 requires clients to ensure that, before writing a (non-n il)
value, previous register sets cannot decide a different value. This is trivially satisfied for register
set 0, however, more work is required by clients to satisfy this rule for subsequent register sets.
Assume each client maintains their own local copy of the state table. Initially, each client’s
state table is empty as they have not yet learned anything regarding the state of the servers. A
client can populate its state tables by reading registers and storing the results in its copy of the
state table. Since the registers are persistent and write-once, if a register contains a value (nil or
otherwise) then any reads will always remain valid. Each client’s state tables will therefore always
contain a subset of the values from the state table.
Fr om its local state table, each client can track whether decisions have been reached or could
be reached by previous quorums . We refer to this as the decision table. At any given time, each
quorum is in one of four decision states:
• Any: Any value could be decided by this quorum.
• Maybe v: If this quorum reaches a decision, then value v will be decided.
• Decided v: The value v has been decided by this quorum; a final state.
• None: This quorum will not decide a value; a final state.
The r ules for updating the decision table are as follows: Initially, the decision state of all
quorums is Any. If there is a quorum where all registers contain the s ame value v then its decision
4