Byzantine agreement is a fundamental problem in fault-tolerant distributed networks that has been studied intensively for the last four decades. Most of these works designed protocols for \emph{complete} networks. A key goal in Byzantine protocols is to tolerate as many Byzantine nodes as possible --- up to $O(n)$ Byzantine nodes ($n$ is the total network size).

The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was the first to address the Byzantine agreement problem in \emph{sparse, bounded degree} networks and presented a protocol that achieved \emph{almost-everywhere} agreement among honest nodes.
In such networks, all known Byzantine agreement protocols (e.g., Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King, Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine nodes had a major drawback that they were \emph{not fully-distributed} --- in those protocols, nodes are required to have initial knowledge of the entire network topolog