CMU-CS-19-134Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-19-134
Hanjun Li M.S. Thesis December 2019
Keywords:
Distributed Algorithm, Byzantine Agreement
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
Srinivasan Seshan, Head, Computer Science Department
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |