Title:Goldfish: Peer selection using Matrix completion in unstructured P2P network

Abstract:Peer-to-peer (P2P) networks underlie a variety of decentralized paradigms including blockchains, distributed file storage and decentralized domain name systems. A central primitive in P2P networks is the peer selection algorithm, which decides how a node should select a fixed number of neighbors to connect with. In this paper, we consider the design of a peer-selection algorithm for unstructured P2P networks with the goal of minimizing the broadcast latency. We propose Goldfish, a novel solution that dynamically decides the neighbor set by exploiting the past experiences as well as exploring new neighbors. The key technical contributions come from bringing ideas of matrix completion for estimating message delivery times for every possible message for every peer ever connected, and a streaming algorithm to efficiently perform the estimation while achieving good performance. The matrix completion interpolates the delivery times to all virtual connections in order to select the best combination of neighbors. Goldfish employs a streaming algorithm that only uses a short recent memory to finish matrix interpolation. When the number of publishing source is equal to a node's maximal number of connections, Goldfish found the global optimal solution with 92.7% probability by exploring every node only once. In more complex situations where nodes are publishing based on exponential distribution and adjusting connection in real time, we compare Goldfish with a baseline peer selection system, and show Goldfish saves approximately 14.5% less time under real world geolocation and propagation latency.