Peer-to-Peer (P2P) networks — typically overlays on top of the Internet — pose some unique challenges to algorithm designers. Primarily, the difficulty comes from heavy churn owing to the short life span of most nodes in the network. Reminiscent of Theseus’ paradox, most nodes in a typical P2P network churn out within an hour only to be replenished with incoming new nodes. In order to maintain a well-connected network despite churn at this level, the overlay has to be constantly reworked. This results in the overlay network graphs being a dynamic graphs that exhibits both edge dynamism and heavy node churn. In this talk, we will discuss how to design fast algorithms that are robust against such dynamic networks.