Message efficient Byzantine Reliable Broadcast protocols on known topologies

Bachelor thesis (2021)

Authors

T.P.D. Anema Electrical Engineering, Mathematics and Computer Science

Contributors

Jérémie Decouchant Data-Intensive Systems - EEMCS (mentor)
K.G. Langendoen Embedded Systems - EEMCS (coach)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2021 Tim Anema
More Info
expand_more

Published Date

01-07-2021

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

In this paper, we consider the Reliable Communication and Byzantine Reliable Broadcast problems on partially connected networks with authenticated links. We consider the Reliable Communication (RC) problem on partially connected networks, and the Byzantine Reliable Broadcast (BRB) problem on partially and fully connected networks. Danny Dolev's protocol works on the former, while Gabriel Bracha's authenticated double echo protocol works on the latter in the case of a fully connected network. By layering the two protocols the BRB problem can be solved for partially connected networks. The state-of-the-art protocols for these problems focus on unknown topologies, whereas we focus on known topologies. We show that these protocols can be optimized when processes leverage this knowledge. Our simulations with our profiler show that we can drastically reduce the message complexity and network usage (e.g., a reduction of 71.9% and 79.4% respectively with a 12B payload when N=150 and f=20 for Dolev) compared to naive routing with our optimizations and disjoint path solver.