Computer Science Masters Thesis Presentation

  • HANJUN LI
  • Masters Student
  • Computer Science Department
  • Carnegie Mellon University
Master's Thesis Presentation

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, Please Contact: 
Keywords: