Most replicated state machines are taught through logs. Raft and Multi-Paxos agree on a sequence of commands, replicate that sequence, and replay commands in the same order at every replica. CASPaxos takes a different route: it replicates the current state value itself and changes that value by applying a user-provided function inside a Paxos-style prepare and accept protocol.
The CASPaxos paper describes a wait-free, linearizable, multi-writer multi-reader register for unreliable asynchronous networks. The register supports arbitrary update operations, including compare-and-set, by treating each command as a change function from current state to next state. The Go implementation linked in this batch is useful because it translates the paper into concrete proposer, preparer, accepter, ballot, quorum, and cluster-change interfaces.
The practical lesson is that consensus does not always require an ever-growing command log. For key-value style workloads, small replicated objects, and systems where write amplification matters, a state-replication design can avoid log management complexity while still relying on quorum intersection and monotonically increasing ballots for safety.
A CASPaxos command is a function that accepts the current state and returns a new state. Instead of ordering commands in a log, the proposer first discovers the latest accepted state from a quorum, applies the function locally, then asks a quorum to accept the resulting state.
Proposers handle protocol behavior and maintain a monotonically increasing ballot counter. Acceptors hold durable state: the accepted ballot, accepted value, and a promise that prevents older ballots from overwriting newer knowledge. This separation mirrors Paxos but removes the replicated log slots common in Multi-Paxos systems.
CASPaxos still uses two familiar phases. In prepare, a proposer gathers the highest accepted value from a quorum. In accept, it writes the transformed state to a quorum. Safety comes from quorum intersection: a later prepare must observe enough acceptors to discover a previously accepted state or a newer competing ballot.
The logless design shifts the replication unit from “command at slot N” to “state value protected by ballot B.” That removes replay machinery but makes each update function responsible for deriving a safe next value from the most recent state observed through quorum reads.
A proposer increments its ballot, sends prepare requests, waits for a quorum of confirmations, chooses the value with the highest accepted ballot, applies the change function, then sends accept requests for the new state. If it sees conflicts with higher ballots, it can fast-forward its local counter before retrying.
type Ballot struct {
Counter uint64
ID string
}
type State []byte
type ChangeFunc func(current State) State
type Preparer interface {
Prepare(b Ballot) (state State, accepted Ballot, err error)
}
type Accepter interface {
Accept(b Ballot, next State) error
}The proposer does not need every acceptor. It needs a quorum. Among successful prepare responses, it selects the returned state whose accepted ballot is highest. If all returned states are empty, the command starts from an empty initial value. This is the read side of the read-modify-write cycle.
func chooseWinningState(results []PrepareResult, quorum int) (State, error) {
var highest Ballot
var winning State
confirmations := 0
for _, r := range results {
if r.Err != nil {
continue
}
confirmations++
if r.Accepted.GreaterThan(highest) {
highest = r.Accepted
winning = r.State
}
}
if confirmations < quorum {
return nil, ErrNoQuorum
}
return winning, nil
}After applying the change function, the proposer sends the new state with the same ballot to acceptors. An acceptor rejects the request if it has already promised or accepted a greater ballot. Otherwise it clears the promise, records the accepted ballot, and persists the new state.
CASPaxos maps naturally to key-value storage where each key is an independent replicated register. The key is attached to prepare and accept messages, and acceptors keep separate accepted state per key. A proposer can reuse one ballot counter across keys because ballots only need to be globally comparable, not consecutive per key.
Compare-and-set is just a change function that inspects the current state and either returns a modified state or returns the current value unchanged. This allows conditional updates to remain linearizable without introducing a separate lock service.
Logless state replication works best when state values are reasonably compact or when the system can encode changes efficiently. It is less attractive for large mutable objects where every accepted value would be expensive to serialize, transfer, or persist.
The Go implementation highlights a subtle cluster-change requirement: proposers may need distinct preparer and accepter sets. During acceptor addition, the new node can first join the accept phase, receive an identity transition, and only later join the prepare phase. That sequencing preserves quorum safety while an initially empty node catches up.
type Proposer interface {
Propose(key string, f ChangeFunc) (State, error)
AddAccepter(target Accepter) error
AddPreparer(target Preparer) error
RemovePreparer(target Preparer) error
RemoveAccepter(target Accepter) error
}When a proposer receives conflicts from acceptors with higher ballots, retrying with the next local counter may fail repeatedly. A practical implementation records the highest conflicting ballot and advances its counter beyond that value before the next proposal.
Deletes require care because a missing value can be confused with an uninitialized value. CASPaxos uses tombstones followed by background cleanup. Cleanup must replicate an empty value to all nodes, not merely a quorum, before old state can be reclaimed safely.