CASPaxos: Replicated State Machines without logs.

CASPaxos is a replicated state machine (RSM) protocol, an extension of Synod.Unlike Raft and Multi-Paxos, it doesn't use leader election and logreplication, thus avoiding associated complexity. Its symmetric peer-to-peerapproach achieves optimal commit latency in wide-area networks and doesn'tcause transient unavailability when any $\lfloor \frac{N-1}2 \rfloor$ of $N$nodes crash.

The lightweight nature of CASPaxos allows new combinations of RSMs in thedesigns of distributed systems. For example, a representation of a key-valuestorage as a hashtable with independent RSM per key increases fault toleranceand improves performance on multi-core systems compared with a hashtable behinda single RSM.

This paper describes CASPaxos protocol, formally proves its safetyproperties, covers cluster membership change and evaluates the benefits of aCASPaxos-based key-value storage.