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 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 parameterize 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 a protocol that runs in expected polynomial round assuming δ > 2α. If we further assume α ≤ 1/2 - ε for any constant ε, the protocol runs in expected constant round. We also show the tightness of our assumptions by proving impossibility results for α ≥ 1/2 and for δ ≤ 2α.

32 pages

Thesis Committee:
Vipul Goyal (Chair)
Bryan Parno

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu