{"id":{"repo_id":"buffalo","oai_identifier":"oai:ubir.buffalo.edu:10477/86475"},"canonical_url":"https://search.dev.ndltd.org/etd/buffalo/oai:ubir.buffalo.edu:10477/86475","repository":{"repo_id":"buffalo","name":"Buffalo","base_url":"https://ubir.buffalo.edu/oai/request"},"display":{"title":"Consensus End-to-End: Design, Implementation, and Evaluation of Consensus Protocols","abstract":"Ph.D.","abstract_html":"Ph.D.","abstract_has_math":false,"creators":["Charapko, Aleksey; 0000-0002-8072-0125"],"institution":"State University of New York at Buffalo","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Demirbas, Murat","Computer Science and Engineering"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-02-21T17:22:48Z","date_published":"2025-02-21T17:22:48Z","updated_at":"2026-07-27T19:05:32Z","subjects":["computer science"],"languages":["eng"],"rights":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10477/86475","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Demirbas, Murat","Computer Science and Engineering"]},{"key":"dc:creator","label":"Author","values":["Charapko, Aleksey; 0000-0002-8072-0125"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-02-21T17:22:48Z","2020"]},{"key":"dc:publisher","label":"Institution","values":["State University of New York at Buffalo"]},{"key":"dc:type","label":"Dc Type","values":["Text","Dissertation"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/10477/86475"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ph.D.","Distributed consensus lies at the heart of most distributed and cloud systems. Various consensus algorithms help with strongly consistent data replication, distributed coordination, application metadata management, and more. However, despite its widespread use and adoption, consensus remains a challenging area of distributed computing. Paxos is one of the most prominent consensus algorithms. It gave rise to a plethora of new protocols and optimizations over the past two decades. Many of these Paxos-derived algorithms improve on some aspects of protocol operation relevant to a particular environment or workload. For example, there are Paxos variants optimized to run on network switches or protocols designed for better WAN performance. The abundance of such special-purpose protocols means that there is no one-fit-all solution. As a result, it becomes increasingly important to evaluate and compare the consensus protocols and systems from the merit of their design, ease, and quality of implementation and performance under different conditions. In this thesis, we propose an end-to-end approach to distributed consensus useful both to protocol designers and practitioners searching for a consensus solution for their system. In the end-to-end consensus, we look at the challenges of distributed consensus design, implementation, evaluation, and practical use. While tools like TLA+ provide powerful abstractions to formally specify and check protocols during the design phase, invariant based reasoning is largely absent at the implementation and evaluation phases. We have developed Retroscope, a monitoring system that brings the invariant based reasoning of a model checker to the runtime. With Retroscope one can search for global predicates and invariants against a running system to help identify bugs and ensure that the key properties transfer from the design to the code. On the implementation side of things, we have created our Paxi framework to facilitate fair performance comparison and evaluation. Paxi levels the playing field by providing common building blocks for developing the protocols, and assuring that implementation details do not affect performance. For evaluations, Paxi includes a powerful micro-benchmarking suite that can generate a variety of workloads for consensus systems. In addition to Paxi benchmarking, our consensus evaluation includes analytical performance modeling to show the theoretical limits of the protocols and their performance under various conditions without tedious and costly experiments. With the help of our end-to-end approach, we not only identified several problems in the Paxos family of protocols, but also designed two distinct solutions for one of these problems. In a study of different consensus architectures, we illustrate some issues like the bottlenecked leaders, performance variances in WAN due to geography, and impacts of command conflicts on the protocols. We then use the end-to-end approach to design two protocols to tackle a leader bottleneck problem identified earlier. Our Paxos Quorum Reads (PQR) algorithm offloads linearizable read operations from the stable leader of a Paxos-backed replicated state machine by allowing clients to read directly from the quorum of followers. PQR shows up to 15% throughput improvement compared to non-PQR replicated state machines, while maintaining the same consistency guarantees. Our PigPaxos protocol takes a different approach and offloads some communication away from the leader to allow scaling a single-leader cluster up to 25 nodes, or 5 times the typical Paxos cluster size, with little performance degradation.","**To request an accessible version of the file(s) associated with this item, contact library@buffalo.edu. Please include the item's persistent URL [http://hdl.handle.net/. . .] in your request.**"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Consensus End-to-End: Design, Implementation, and Evaluation of Consensus Protocols"]}]}],"canonical_facts":{"dc:contributor":["Demirbas, Murat","Computer Science and Engineering"],"dc:creator":["Charapko, Aleksey; 0000-0002-8072-0125"],"dc:date":["2025-02-21T17:22:48Z","2020"],"dc:description":["Ph.D.","Distributed consensus lies at the heart of most distributed and cloud systems. Various consensus algorithms help with strongly consistent data replication, distributed coordination, application metadata management, and more. However, despite its widespread use and adoption, consensus remains a challenging area of distributed computing. Paxos is one of the most prominent consensus algorithms. It gave rise to a plethora of new protocols and optimizations over the past two decades. Many of these Paxos-derived algorithms improve on some aspects of protocol operation relevant to a particular environment or workload. For example, there are Paxos variants optimized to run on network switches or protocols designed for better WAN performance. The abundance of such special-purpose protocols means that there is no one-fit-all solution. As a result, it becomes increasingly important to evaluate and compare the consensus protocols and systems from the merit of their design, ease, and quality of implementation and performance under different conditions. In this thesis, we propose an end-to-end approach to distributed consensus useful both to protocol designers and practitioners searching for a consensus solution for their system. In the end-to-end consensus, we look at the challenges of distributed consensus design, implementation, evaluation, and practical use. While tools like TLA+ provide powerful abstractions to formally specify and check protocols during the design phase, invariant based reasoning is largely absent at the implementation and evaluation phases. We have developed Retroscope, a monitoring system that brings the invariant based reasoning of a model checker to the runtime. With Retroscope one can search for global predicates and invariants against a running system to help identify bugs and ensure that the key properties transfer from the design to the code. On the implementation side of things, we have created our Paxi framework to facilitate fair performance comparison and evaluation. Paxi levels the playing field by providing common building blocks for developing the protocols, and assuring that implementation details do not affect performance. For evaluations, Paxi includes a powerful micro-benchmarking suite that can generate a variety of workloads for consensus systems. In addition to Paxi benchmarking, our consensus evaluation includes analytical performance modeling to show the theoretical limits of the protocols and their performance under various conditions without tedious and costly experiments. With the help of our end-to-end approach, we not only identified several problems in the Paxos family of protocols, but also designed two distinct solutions for one of these problems. In a study of different consensus architectures, we illustrate some issues like the bottlenecked leaders, performance variances in WAN due to geography, and impacts of command conflicts on the protocols. We then use the end-to-end approach to design two protocols to tackle a leader bottleneck problem identified earlier. Our Paxos Quorum Reads (PQR) algorithm offloads linearizable read operations from the stable leader of a Paxos-backed replicated state machine by allowing clients to read directly from the quorum of followers. PQR shows up to 15% throughput improvement compared to non-PQR replicated state machines, while maintaining the same consistency guarantees. Our PigPaxos protocol takes a different approach and offloads some communication away from the leader to allow scaling a single-leader cluster up to 25 nodes, or 5 times the typical Paxos cluster size, with little performance degradation.","**To request an accessible version of the file(s) associated with this item, contact library@buffalo.edu. Please include the item's persistent URL [http://hdl.handle.net/. . .] in your request.**"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/10477/86475"],"dc:language":["eng"],"dc:publisher":["State University of New York at Buffalo"],"dc:rights":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."],"dc:subject":["computer science"],"dc:title":["Consensus End-to-End: Design, Implementation, and Evaluation of Consensus Protocols"],"dc:type":["Text","Dissertation"]},"updated_at":"2026-07-27T19:05:32Z"}