  The celebrated result of Fischer, Lynch and Paterson is the fundamental lower
bound for asynchronous fault tolerant computation: any 1-crash resilient
asynchronous agreement protocol must have some (possibly measure zero)
probability of not terminating. In 1994, Ben-Or, Kelmer and Rabin published a
proof-sketch of a lesser known lower bound for asynchronous fault tolerant
computation with optimal resilience against a Byzantine adversary: if $n\le 4t$
then any t-resilient asynchronous verifiable secret sharing protocol must have
some non-zero probability of not terminating.
  Our main contribution is to revisit this lower bound and provide a rigorous
and more general proof. Our second contribution is to show how to avoid this
lower bound. We provide a protocol with optimal resilience that is almost
surely terminating for a strong common coin functionality. Using this new
primitive we provide an almost surely terminating protocol with optimal
resilience for asynchronous Byzantine agreement that has a new fair validity
property. To the best of our knowledge this is the first asynchronous Byzantine
agreement with fair validity in the information theoretic setting.
