Generalized Consensus for Practical Fault-Tolerance

Despite extensive research on Byzantine Fault Tolerant (BFT) systems, overheads associated with such solutions preclude widespread adoption. Past efforts such as the Cross Fault Tolerance (XFT) model address this problem by making a weaker assumption that a majority of processes are correct and communicate synchronously. Although XPaxos of Liu et al. (using the XFT model) achieves similar performance as Paxos, it does not scale with the number of faults. Also, its reliance on a single leader introduces considerable downtime in case of failures. This thesis presents Elpis, the first multi-leader XFT consensus protocol. By adopting the Generalized Consensus specification from the Crash Fault Tolerance model, we were able to devise a multi-leader protocol that exploits the commutativity property inherent in the commands ordered by the system. Elpis maps accessed objects to non-faulty processes during periods of synchrony. Subsequently, these processes order all commands which access these objects. Experimental evaluation confirms the effectiveness of this approach: Elpis achieves up to 2x speedup over XPaxos and up to 3.5x speedup over state-of-the-art Byzantine Fault-Tolerant Consensus Protocols.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Engineering

Department dc:contributor.department

Electrical and Computer Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2018

Author dc:creator

• Garg, Mohit

Chair dc:contributor.committeechair

• Ravindran, Binoy

Committee members dc:contributor.committeemember

• Min, Changwoo
• Peluso, Sebastiano

• Distributed Systems
• Fault Tolerance
• Byzantine Fault Tolerance
• State Machine Replication
• Multi-Leader Consensus
• Blockchain

Statement dc:rights

• Creative Commons Attribution-ShareAlike 3.0 United States

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-nc-sa/3.0/us/

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/10919/85049

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/85049