  The Byzantine agreement problem is considered to be a core problem in
distributed systems. For example, Byzantine agreement is needed to build a
blockchain, a totally ordered log of records. Blockchains are asynchronous
distributed systems, fault-tolerant against Byzantine nodes.
  In the literature, the asynchronous byzantine agreement problem is studied in
a fully connected network model where every node can directly send messages to
every other node. This assumption is questionable in many real-world
environments. In the reality, nodes might need to communicate by means of an
incomplete network, and Byzantine nodes might not forward messages.
Furthermore, Byzantine nodes might not behave correctly and, for example,
corrupt messages. Therefore, in order to truly understand Byzantine Agreement,
we need both ingredients: asynchrony and incomplete communication networks.
  In this paper, we study the asynchronous Byzantine agreement problem in
incomplete networks. A classic result by Danny Dolev proved that in a
distributed system with n nodes in the presence of f Byzantine nodes, the
vertex connectivity of the system communication graph should be at least
(2f+1). While Dolev's result was for synchronous deterministic systems, we
demonstrate that the same bound also holds for asynchronous randomized systems.
We show that the bound is tight by presenting a randomized algorithm, and a
matching lower bound.
