• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedUser profile (HSE staff only)SearchMenu

Byzantine Fault-Tolerant Distributed Computing: Reconfiguration and Consensus

Student: Andrei Tonkikh

Supervisor: Denis Moskvin

Faculty: St. Petersburg School of Physics, Mathematics, and Computer Science

Educational Programme: Software Development and Data Analysis (Master)

Year of Graduation: 2021

Byzantine fault-tolerance is a critical mechanism allowing software engineers to build distributed systems resilient to numerous kinds of hardware failures, software bugs, and security breaches. Depending on the environment, different models are used to design distributed protocols. Notably, there is a huge gap between the so-called asynchronous and partially-synchronous models. The latter allows for deterministic solutions of the famous consensus problem whereas the former does not. In this thesis, one important problem for each of the two models is addressed, the ultimate goal being to make both types of algorithms more applicable in practice. In the asynchronous model, the problem of reconfiguration is considered. Most known Byzantine fault-tolerant algorithms are designed with the assumption that the set of processes executing the protocol is fixed and known a priori. While being very convenient for algorithm designers, this assumption is not very realistic. In practice, servers often need to be replaced, repaired, or added for greater fault tolerance. In this thesis, the first asynchronous reconfiguration protocol tolerating Byzantine failures is presented. In the partially-synchronous model, on the other hand, reconfiguration can be performed much easier thanks to the possibility to solve consensus. However, Byzantine fault-tolerant consensus algorithms have a reputation of being much slower than their crash fault-tolerant counterparts. To close this gap, the class of fast Byzantine consensus algorithms has emerged. These algorithms aim at solving the Byzantine consensus with the same latency as crash fault-tolerant solutions. However, this improved latency comes at the cost of decreased fault tolerance. In this thesis, a new fast Byzantine consensus algorithm that has better resilience than any of the previously existing ones is presented. Moreover, the algorithm comes with proof that its resilience is optimal. The surprising discovery is that, in the special yet very important in practice case when only one Byzantine failure is tolerated, the algorithm presented in this thesis requires only 4 processes, which remains optimal even if we allow for suboptimal latency. All previously known fast Byzantine consensus algorithms required at least 6 processes in this case.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses