  Consensus algorithms are deployed in the wide area to achieve high
availability for geographically replicated applications. Wide-area consensus is
challenging due to two main reasons: (1) low throughput due to the high latency
overhead of client request dissemination and (2) network asynchrony that causes
consensus protocols to lose liveness. In this paper, we propose Mandator and
Sporades, a modular state machine replication algorithm that enables high
performance and resiliency in the wide-area setting.
  To address the high client request dissemination overhead challenge, we
propose Mandator, a novel consensus-agnostic asynchronous dissemination layer.
Mandator separates client request dissemination from the critical path of
consensus to obtain high performance. Composing Mandator with Multi-Paxos
(Mandator-Paxos) delivers significantly high throughput under synchronous
networks. However, under asynchronous network conditions, Mandator-Paxos loses
liveness which results in high latency. To achieve low latency and robustness
under asynchrony, we propose Sporades, a novel omission fault-tolerant
consensus algorithm. Sporades consists of two modes of operations --
synchronous and asynchronous -- that always ensure liveness. The combination of
Mandator and Sporades (Mandator-Sporades) provides a robust and high-performing
state machine replication system.
  We implement and evaluate Mandator-Sporades in a wide-area deployment running
on Amazon EC2. Our evaluation shows that in the synchronous execution,
Mandator-Sporades achieves 300k tx/sec throughput in less than 900ms latency,
outperforming Multi-Paxos, EPaxos and Rabia by 650\% in throughput, at a modest
expense of latency. Furthermore, we show that Mandator-Sporades outperforms
Mandator-Paxos, Multi-Paxos, and EPaxos in the face of targeted distributed
denial-of-service attacks.

Distributed, Parallel, and Cluster Computing