Strongly consistent coordination services for distributed applications do not scale well over wide-area networks (WAN): centralized coordination fails to scale with respect to the increasing distances in WAN, and fully distributed coordination fails to scale with respect to the number of nodes involved. We show in this thesis that it is possible to achieve scalability for strongly consistent coordination over WAN using hierarchical and decentralized coordination architecture and smart/dynamic migration mechanisms. We lay down the foundation of two novel designs for coordination frameworks, called WanKeeper and WPaxos.

Both WanKeeper and WPaxos frameworks achieve fast wide-area coordination by dynamically partitioning the objects across multiple leaders. WanKeeper introduces a framework that extends centralized coordination by hierarchical composition and token migration ideas and combines the benefits of both centralized and decentralized coordination approaches. WPaxos introduces a multi-leader Paxos protocol that provides low-latency and high-throughput consensus across WAN deployments. Unlike statically partitioned multiple Paxos deployments, WPaxos perpetually adapts to the changing access locality through object stealing. WPaxos employs a flexible grid quorum that is more suitable for WAN setting with tunable fault-tolerance parameters.

The decentralization and emphasis on local operations allows the protocols to significantly outperform other WAN Paxos solutions, while maintaining the same consistency guarantees. During the study of the full spectrum of WAN coordination protocols, we developed a general framework Paxi that allow us to fast prototype many protocols, benchmark their consistency invariant, availability and performance. We investigated limitations of multiple data migration policies for better adaptation to access locality. We have shown that it is possible to achieve low latency, high throughput and strongly consistent coordination over wide area networks by utilizing (1) efficient architecture, (2) locality-awareness algorithms, and (3) smart migration policy. Our experimental results show that decentralized frameworks provide multiple folds improvement of performance in WAN compared to fully centralized or distributed solutions.