CNS Core: Small: Paxos Unpacked

Suny At Buffalo, Amherst NY

Investigators

Abstract

Due to their excellent fault-tolerance properties, Paxos protocols have been employed by many cloud computing systems for consistent coordination of clusters of computers. This project aims to show that when properly customized, Paxos family of protocols can also deliver top-notch performance and scalability, which they currently lack. To this end, the project will design high-performance, scalable, practical, and usable Paxos variants customized for different deployments and use cases. Instead of developing disjoint point-solutions, the project will provide a systematic and principled exploration of the solution space. Scaling Paxos and making it practical and customizable involves many challenges and requires an assortment of distributed algorithmic tools and techniques. For scaling Paxos horizontally, the project will investigate novel in-protocol sharding and reconfiguration strategies enabled by the flexible quorums result. For scaling Paxos vertically, the project will alleviate the bottleneck at the leaders by decoupling control from communication flow and by employing in-protocol aggregation optimizations. To provide consensus as a lightweight serverless primitive, the project will develop efficient single-instance fine-granularity consensus as a systems primitive and showcase its use in applications. The techniques developed in this project will have broader applicability to coordination protocols in general. In order to accelerate technology transfer to academia and industry, the project will showcase these techniques in the context of a globally distributed database prototype. The project will also enable broader impact through enhancing scientific/technological understanding, distributing tools and software to the community, engaging undergraduate and underrepresented students, and reaching out to K-12 students. New tools, software, and material will be created to teach students the principles of distributed systems and reasoning about distributed protocols. The project will share all the software, documentation, and technical papers generated with the public openly as open source via Github repositories at https://github.com/muratdem. These material will include TLA+/Pluscal models of the protocols, implementations of the protocols in Go language, implementation of a distributed database showcasing the protocols, implementation of primitives and tools for designing and developing coordination protocols, course modules on distributed coordination, research papers, presentations, and blog posts. The material will be stored and preserved for at least three years beyond the award period. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.