Bounding the Communication Complexity of Fault-Tolerant Common Coin Tossing

Ivan Geffner, Joseph Y. Halpern

Protocols for tossing a common coin play a key role in the vast majority of implementations of consensus. Even though the common coins in the literature are usually \emph{fair} (th…