Purdue University Graduate School
Browse

Pipelined Byzantine Fault Tolerance and Applications

Download (4.49 MB)
thesis
posted on 2023-12-07, 16:01 authored by Adithya BhatAdithya Bhat

Practically, Byzantine faults are not assumed in cloud applications. Byzantine fault-tolerance adds significant cryptographic, communication, throughput, and latency overheads to applications, contributing to the resistance towards its widespread adoption. Existing Byzantine-fault tolerant protocols focus on optimal latency or optimal communication while ignoring the throughput and cryptographic overheads.

In this thesis, we explore pipelining for Byzantine fault-tolerant applications. Pipelining tasks is a common optimization in distributed systems that involves executing tasks in stages. The idea is that instead of executing a task in an iteration as an atomic unit, we split the execution into stages and execute all stages of different tasks per iteration. We observe significant performance benefits if executing later stages of a task helps other tasks in earlier stages, saving effort in each stage. The length of the pipeline, i.e., the number of stages, determines the latency of an individual task. However, if the pipeline improves the execution of every stage enough, then the latency improves.

We primarily explore three Byzantine Fault Tolerant (BFT) applications with pipelining: (i) unique chain-based State Machine Replication protocols: Apollo, Artemis, Leto, and Zeus, and (ii) energy-efficient State Machine Replication: EESMR. (iii) random beacon protocols: GRandPiper, BRandPiper, and OptRand. We design them with a pipeline-first approach to improve the throughput, cryptographic, and communication costs at every stage of the pipeline. With respect to latency, we show (i) pipelined SMR protocols where our pipeline stages have constant cryptographic and linear communication costs allowing our protocols to outperform state-of-the-art BFT-SMR protocols in throughput. (ii) pipelined SMR protocols with techniques to make each stage of the pipeline independent, thus achieving demonstrable energy efficiency while allowing an unbounded number of non-interactive parallel proposals. (iii) reduced latencies for reconfiguration-friendly random beacons by using two pipelines: an SMR pipeline to commit and a beacon pipeline to produce random numbers and decoupling the two pipelines thereby removing the impact of the high-latency SMR pipeline on the latency of the randomness output by the system.

Funding

W911NF-20-2-0026 Army Research Laboratory (ARL)

Collaborative Research: CPS: Medium: Secure CPS for Real-time Agro-Analytics

National Institute of Food and Agriculture

Find out more...

CAREER: Towards Privacy and Availability of Inter-blockchain Communication

Directorate for Computer & Information Science & Engineering

Find out more...

History

Degree Type

  • Doctor of Philosophy

Department

  • Computer Science

Campus location

  • West Lafayette

Advisor/Supervisor/Committee Chair

Aniket Kate

Additional Committee Member 2

Saurabh Bagchi

Additional Committee Member 3

Michael K Reiter

Additional Committee Member 4

Yongle Zhang

Additional Committee Member 5

Vassilis Zikas

Usage metrics

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC