Bachelor/Master Thesis
Validity in Byzantine Consensus
Byzantine consensus allows processes to decide on a common value in the presence of Byzantine processes. Three properties of Byzantine consensus [1] are
- Termination: Every process eventually decides some value,
- Integrity: No correct process decides twice,
- Agreement: No two correct processes decide differently.
A fourth property is ‘validity’ and the definition may differ depending on the type or context of Byzantine consensus. Besides, the domain of a Byzantine consensus protocol plays an important role, i.e., whether it may decide on binary values, values from a small set, or values from (exponentially) large sets. Definitions for the validity property in standard textbooks [1] include weak validity, strong validity, and external validity. Additionally, Fitzi and Garay [2] formulate delta-differential consensus satisfying delta-differential validity property.
The goal of the thesis is to analyze, compare, and find connections among the different notions of validity.
Requirements: Interest in conceptual thinking, and knowledge of distributed protocols [3].
References
[1] Introduction to Reliable and Secure Distributed Programming
[2] Efficient Player-Optimal Protocols for Strong and Differential Consensus
[3] Distributed Algorithms FS2022