Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Rex: Replication at the Speed of Multi-core

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


Standard state-machine replication involves consensus on a sequence of totally ordered requests through, for example, the Paxos protocol. Such a sequential execution model is becoming outdated on prevalent multi-core servers. Highly concurrent executions on multi-core architectures introduce non-determinism related to thread scheduling and lock contentions, and fundamentally break the assumption in state-machine replication. 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. Concurrent executions of the application can be decoupled with a sequence of consensus decisions through consensus on partial-order traces, rather than on totally ordered requests, that capture the non-deterministic decisions in one replica execution and to be replayed with the same decisions on others. The result is a new multi-core friendly replicated state-machine framework that achieves strong consistency while preserving parallelism in multi-thread 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 16 times the throughput of standard replicated state machines.


Publication typeInproceedings
Published inEuroSys '14: Proceedings of the Ninth European Conference on Computer Systems
> Publications > Rex: Replication at the Speed of Multi-core