Fast Mencius: Mencius with low commit latency

Mencius is a protocol for general state machine replication that tolerates crash failures. It has high performance in wide-area networks. However, the commit latency of Mencius is limited by the slowest replica. This paper presents Fast Mencius, a crash fault-tolerant state machine replication protocol, which enhances Mencius with Active Revoke and Multi-instance Propose. Active Revoke allows the non-slow replicas to proceed without being delayed by the slowest replica, while Multi-instance Propose enables the slow replicas to have their proposals chosen by the replicated state machine. Our evaluation shows that in presence of slow replicas, Fast Mencius´s commit latency is significantly lower than that of Mencius, and it also achieves high throughput.