Computer Science Masters Thesis Presentation

Tuesday, December 3, 2019 - 2:00pm

Location:

4220 Wean Hall

Speaker:

HANJUN LI, Masters Student https://www.linkedin.com/in/hanjun-li-71bb7489

Byzantine Agreement with Incomplete Views

Byzantine agreement is the problem where a set of participants, each holding an input value, try to reach agreement on an output in the presence of corrupted parties. This problem is well studied in the standard model, where the each participant has a complete view of the whole network. This thesis solves the byzantine agreement problem in a relaxed model where every participant only knows and communicates with a subset (its “view”) of other parties. We parametrize our model by α, the maximum fraction of corruption in each honest “view”, and δ, the minimum fraction of overlapping between any pair of honest “views”. We present an expected linear round protocol assuming δ  > 2α,  an expected constant round protocol assuming further α ≤ 1/2 − ε for any constant ε. We also show the tightness of our assumption by impossibility results for α ≥ 1/2 and for δ ≤ 2α.

Thesis Committee:
Vipul Goyal
Bryan Parno

Additional Thesis Information

For More Information, Contact:

Keywords:

Master's Thesis Presentation