PAXOS Made Transparent

State machine replication (SMR) leverages distributed con-sensus protocols such as PAXOS to keep multiple replicas of a program consistent in face of replica failures or network partitions. This fault tolerance is enticing on implementing a principled SMR system that replicates general programs, es-pecially server programs that demand high availability. Un-fortunately, SMR assumes deterministic execution, but most server programs are multithreaded and thus nondeterminis-tic. Moreover, existing SMR systems provide narrow state machine interfaces to suit specific programs, and it can be quite strenuous and error-prone to orchestrate a general pro-gram into these interfaces This paper presents CRANE, an SMR system that transpar-ently replicates general server programs. CRANE achieves distributed consensus on the socket API, a common interface to almost all server programs. It leverages deterministic mul-tithreading (specifically, our prior system PARROT) to make multithreaded replicas deterministic. It uses a new technique we call time bubbling to efficiently tackle a difficult chal-lenge of nondeterministic network input timing. Evaluation on five widely used server programs (e.g., Apache, ClamAV, and MySQL) shows that CRANE is easy to use, has mod-erate overhead, and is robust. CRANE’s source code is at github.com/columbia/crane