Consensus in Blockchain: from Gossip to Synchronous Byzantine Fault Tolerance

You are cordially invited to attend the PhD Dissertation Defence of Nenad Milosevic on Thursday 26 September 2024 at 16:30 in room D0.03.

Abstract:
State machine replication and consensus are crucial for the reliability and robustness of distributed systems. This thesis examines these problems in the context of modern decentralized systems, particularly blockchains. Specifically, it explores the integration of gossip communication with consensus protocols and investigates synchronous Byzantine fault-tolerant (BFT) consensus protocols. We first explore the impact of gossip-based communication on consensus protocols, using the Paxos algorithm as a case study. We introduce Semantic Gossip, which optimizes gossip communication through semantic filtering and aggregation. Experimental results demonstrate that Semantic Gossip reduces message overhead and improves performance while maintaining reliability. Next, we assess the robustness of synchronous BFT consensus protocols under synchrony violations and Byzantine attacks. We propose a novel evaluation methodology and apply it to a new protocol, Sync Tendermint, showing that communication diversity and redundancy enable Sync Tendermint to tolerate synchrony violations without compromising correctness, resulting in lower synchrony bounds and enhanced performance. Finally, motivated by experimental data on message delays, we present a hybrid synchronous system model that distinguishes between small and large messages. Within this model, we develop AlterBFT, a BFT consensus protocol that relies on the timely delivery of small messages for agreement while requiring large messages to be eventually timely to ensure progress. Our evaluation shows that AlterBFT achieves significantly lower latency than state-of-the-art synchronous protocols and offers comparable performance and higher resilience than state-of-the-art partially synchronous protocols. This thesis advances the understanding of consensus in partially connected and synchronous environments, providing practical solutions to improve the performance and robustness of distributed systems.

Dissertation Committee:
- Prof. Fernando Pedone, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Patrick Thomas Eugster, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Robert Soulé, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Benoit Garbinato, UNIL, Switzerland (External Member)
- Prof. Marko Vukolic, Protocol Labs (External Member)
- Prof. Josef Widder, Informal Systems, Austria (External Member)