A Low-latency Consensus Algorithm for Geographically Distributed Systems

Simple item page
dc.contributor.authorArun, Balajien
dc.contributor.committeechairRavindran, Binoyen
dc.contributor.committeememberZeng, Haiboen
dc.contributor.committeememberBroadwater, Roberten
dc.contributor.departmentElectrical and Computer Engineeringen
dc.date.accessioned2017-11-02T20:48:44Zen
dc.date.adate2017-05-15en
dc.date.available2017-11-02T20:48:44Zen
dc.date.issued2017-02-28en
dc.date.rdate2017-05-15en
dc.date.sdate2017-03-23en
dc.description.abstractThis thesis presents Caesar, a novel multi-leader Generalized Consensus protocol for geographically replicated systems. Caesar is able to achieve near-perfect availability, provide high performance - low latency and high throughput compared to the existing state-of-the- art, and tolerate replica failures. Recently, a number of state-of-the-art consensus protocols that implement the Generalized Consensus definition have been proposed. However, the major limitation of these existing approaches is the significant performance degradation when application workload produces conflicting requests. Caesar's main goal is to overcome this limitation 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. It only switches to a slow decision if there is no chance to agree on the proposed order for that request. Caesar is able to achieve this using a combination of wait condition and logical time stamping. 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 presence of 30% conflicting requests, and single-leader (e.g., Multi-Paxos) by as much as 3.5x. The protocol is also resistant to heavy client loads unlike existing protocols.en
dc.description.degreeMaster of Scienceen
dc.identifier.otheretd-03232017-095010en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-03232017-095010/en
dc.identifier.urihttp://hdl.handle.net/10919/79945en
dc.language.isoen_USen
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectMulti-Leader Consensusen
dc.subjectState Machine Replicationen
dc.subjectFault Toleranceen
dc.subjectDistributed Systemsen
dc.titleA Low-latency Consensus Algorithm for Geographically Distributed Systemsen
dc.typeThesisen
dc.type.dcmitypeTexten
thesis.degree.disciplineElectrical and Computer Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
etd-03232017-095010_Arun_B_T_2017.pdf
Size:
1.81 MB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Masters Theses