  Randomisation is a critical tool in designing distributed systems. The common
coin primitive, enabling the system members to agree on an unpredictable random
number, has proven to be particularly useful. We observe, however, that it is
impossible to implement a truly random common coin protocol in a fault-prone
asynchronous system.
  To circumvent this impossibility, we introduce two relaxations of the perfect
common coin: (1) approximate common coin generating random numbers that are
close to each other; and (2) Monte Carlo common coin generating a common random
number with an arbitrarily small, but non-zero, probability of failure.
Building atop the approximate agreement primitive, we obtain efficient
asynchronous implementations of the two abstractions, tolerating up to one
third of Byzantine processes. Our protocols do not assume trusted setup or
public key infrastructure and converge to the perfect coin exponentially fast
in the protocol running time.
  By plugging one of our protocols for Monte Carlo common coin in a well-known
consensus algorithm, we manage to get a binary Byzantine agreement protocol
with $O(n^3 \log n)$ communication complexity, resilient against an adaptive
adversary, and tolerating the optimal number $f<n/3$ of failures without
trusted setup or PKI. To the best of our knowledge, the best communication
complexity for binary Byzantine agreement achieved so far in this setting is
$O(n^4)$. We also show how the approximate common coin, combined with a variant
of Gray code, can be used to solve an interesting problem of Intersecting
Random Subsets, which we introduce in this paper.
