Abstract

We provide the first protocol that solves Byzantine agreement with optimal early stopping (min{f+2,t+1} rounds) and optimal resilience (n>3t) using polynomial message size and computation. All previous approaches obtained sub-optimal results and used resolve rules that looked only at the immediate children in the EIG (\emph{Exponential Information Gathering}) tree. At the heart of our solution are new resolve rules that look at multiple layers of the EIG tree.

Files

Date

2015

Authors

Tags

  • Distributed Computing

Booktitle

STOC 2015