  This paper proposes Caesar, a novel multi-leader Generalized Consensus
protocol for geographically replicated sites. The main goal of Caesar is to
overcome one of the major limitations of existing approaches, which is the
significant performance degradation when application workload produces
conflicting requests. Caesar does that by changing the way a fast decision is
taken: its ordering protocol does not reject a fast decision for a client
request if a quorum of nodes reply with different dependency sets for that
request. The effectiveness of Caesar is demonstrated through an evaluation
study performed on Amazon's EC2 infrastructure using 5 geo-replicated sites.
Caesar outperforms other multi-leader (e.g., EPaxos) competitors by as much as
1.7x in the presence of 30% conflicting requests, and single-leader (e.g.,
Multi-Paxos) by up to 3.5x.
