Brief Announcement: A Fully-Distributed Construction of Byzantine-Resilient Dynamic Peer-to-Peer Networks

We address a fundamental problem in Peer-to-Peer (P2P) networks, namely, constructing and maintaining dynamic P2P overlay network topologies with essential properties such as connectivity, low diameter, and high expansion, that are resilient to continuous high churn and the presence of a large number of malicious (Byzantine) nodes. Our main goal is to construct and maintain a sparse (bounded degree) expander topology despite high churn and a large number of Byzantine nodes. Such an expander topology has logarithmic diameter, high expansion, and is robust to churn and the presence of a large number of bad nodes, and facilitates efficient and robust algorithms for fundamental problems in distributed computing, such as agreement, broadcasting, routing, etc.