Bounds on information exchange for Byzantine agreement
Paper: Bounds on information exchange for Byzantine agreement. Danny Dolev, and Rüdiger Reischuk. 1985
- They show that \(\Omega(nt)\) is a lower bound for the number of signatures for any algorithm using authentication.
- For the number of messages in the authenticated case we prove the lower bound \(\Omega(n + t^{2})\).
References
Danny Dolev, and Rüdiger Reischuk. 1985. “Bounds on information exchange for Byzantine agreement.” https://dl.acm.org/doi/10.1145/2455.214112.