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α.