This is the classic "Gnutella problem" of scalability and is still I believe very much an open problem. One runs into it in WebRTC multicast scenarios. But fortunately there are many vendors such as Twilio that provide cloud solutions ;)
Best solution is to overlay a distributed hash table as k-v store over the p2p network. Nodes can then query that instead of each other. You can make your implementation more robust by exploiting and rewarding nodes in the network that have faster net connections, more compute power, etc. Best of luck!
OpenDHT: A C++11 Distributed Hash Table implementation
https://github.com/savoirfairelinux/opendht
