Current peer-to-peer (P2P) file sharing applications are remarkably simple and robust, but their inefficiency can produce very high network loads. The use of super-peers has been proposed to improve the performance of unstructured P2P systems. These have the potential to approach the performance and scalability of structured systems, while retaining the benefits of unstructured P2P systems. There has, however, been little consensus on the best topology for connecting these super-peers, or how to construct the topology in a distributed, robust way.

In this paper we propose a Scalable Unstructured P2P System (SUPS). The unique aspect of SUPS is a protocol for the distributed construction of a super-peer topology that has highly desirable performance characteristics. The protocol is inspired by the theory of random graphs. We describe the protocol, and demonstrate experimentally that it produces a balanced and low-diameter super-peer topology at low cost. We show that the method is very robust to super-peer failures and inconsistent information, and compare it with other approaches.