Synchronous Byzantine Broadcast algorithms for a dishonest majority

This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019Cataloged from student-submitted PDF version of thesis.Includes bibliographical references (page 37).Deterministic Byzantine Broadcast requires f+1 rounds for any f malicious processes, in the synchronous, authenticated setting. In the non-deterministic case, Katz and Koo [2] showed a lower-bound of [omega](2n=(n-f)) rounds, but it remains an open question whether the bound is tight, specically when f >/= n/2 (a dishonest majority). This thesis explores ways to improve the eciency of Byzantine Broadcast algorithms for a dishonest majority. In particular, we present an expected 10 round protocol for f = n/2, which works by constructing a hierarchy of quorums, to gather as many signatures as possible, before commitment. Finally, we offer brief commentary on how similar techniques could extend to f > n/2.by Benjamin Yao Chan.M. Eng.M.Eng. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Scienc