Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Paxos Made Parallel

Zhenyu Guo, Chuntao Hong, Mao Yang, Dong Zhou, Lidong Zhou, and Li Zhuang

Abstract

Standard state-machine replication involves consensus on a sequence of totally ordered requests through, for example, the Paxos protocol. Serialized request processing seriously limits our ability to leverage prevalent multi-core servers. This tension between concurrency and consistency is not inherent because the total-ordering of requests is merely a simplifying convenience that is unnecessary for consistency. Replicated state machines can be made parallel by consensus on partial-order traces, rather than on totally ordered requests, that capture causal orders in one replica execution and to be replayed in an order-preserving manner on others. The result is a new multi-core friendly replicated state-machine framework that achieves strong consistency while preserving parallelism in multi-threaded applications. On 12-core machines with hyper-threading, evaluations on typical applications show that we can scale with the number of cores, achieving up to a 16 times throughput increase over standard replicated state machines.

Details

Publication typeTechReport
NumberMSR-TR-2012-118
> Publications > Paxos Made Parallel