  WPaxos is a multileader Paxos protocol that provides low-latency and
high-throughput consensus across wide-area network (WAN) deployments. WPaxos
uses multileaders, and partitions the object-space among these multileaders.
Unlike statically partitioned multiple Paxos deployments, WPaxos is able to
adapt to the changing access locality through object stealing. Multiple
concurrent leaders coinciding in different zones steal ownership of objects
from each other using phase-1 of Paxos, and then use phase-2 to commit
update-requests on these objects locally until they are stolen by other
leaders. To achieve fast phase-2 commits, WPaxos adopts the flexible quorums
idea in a novel manner, and appoints phase-2 acceptors to be close to their
respective leaders. We implemented WPaxos and evaluated it on WAN deployments
across 5 AWS regions. The dynamic partitioning of the object-space and emphasis
on zone-local commits allow WPaxos to significantly outperform both partitioned
Paxos deployments and leaderless Paxos approaches.
