ACM Symposium on Principles of Distributed Computing (PODC)
Balanced and Adaptively Secure Asynchronous Common Coin and Byzantine Agreement With Sub-Quadratic Communication
Hanwen Feng, Tiancheng Mai, Qiang Tang
Abstract
Distributed common randomness generation (i.e., the common coin problem) is a cornerstone of randomized distributed computing. While a long line of research has sought scalable solutions, the asynchronous setting remains a challenge. Specifically, while Blum et al. (TCC'21) achieved sub-quadratic communication complexity, their approach lacks “balance”: certain nodes must still send Ω(n) messages, creating a scalability bottleneck. Furthermore, their solution only tolerates a 1/3 - ε fraction of corrupted nodes, whereas the classic construction by Cachin et al. (PODC'00) tolerates up to 1/2 under the same setup assumptions.