--An O(log n)-round randomized Byzantine Agreement (BA) protocol in a synchronous fullinformation network tolerating t \le \frac{n} {{3 + \in }} faulty players (for any constant \in \ge 0). As such, our protocol is asymptotically optimal in terms of fault-tolerance.

--An O(1)-round randomized BA protocol in a synchronous full-information network tolerating t = O( \frac{n} {{(\log n)^{1.58} }} ) faulty players.

--A compiler that converts any randomized protocol \prod\nolimits_{in} designed to tolerate t fail-stop faults, where the source of randomness of \prod\nolimits_{in} is an SV-source, into a protocol \prod\nolimits_{out} that tolerates min(t, \frac{n} {3} ) Byzantine faults. If the round-complexity of \prod\nolimits_{in} is r, that of \prod\nolimits_{out} is O(r log* n).

Central to our results is the development of a new tool, "audited protocols". Informally "auditing" is a transformation that converts any protocol that assumes builtin broadcast channels into one that achieves a slightly weaker guarantee, without assuming broadcast channels.

We regard this as a tool of independent interest, which could potentially find applications in the design of simple and modular randomized distributed algorithms.