Strongly Adaptive Asynchronous Byzantine Agreement with Linear Communication and Almost-Everywhere Termination↗ (원문, 새 창)

본문 미리보기

It is well known that Byzantine agreement requires $\Omega(t^2)$ messages against a strongly adaptive adversary that may corrupt $t=\Theta(n)$ parties and suppress a party's undelivered messages upon corruption. We circumvent this lower bound by relaxing termination: for any constant $00$ and every $t\leq(1-\delta)n/3$, we construct binary agreement with this guarantee in authenticated asynchronous networks against strongly adaptive corruptions with message takebacks. Except with negligible pro