A network membership management protocol manages membership in a peer-to-peer networking environment. To join the peer-to-peer network, a new client is introduces itself to a deputy node assigned by the server to act as a point of contact for the new client. The deputy node forwards subscription requests to other neighboring nodes which probabilistically determine whether to accept the subscription request from the new client or forward the message to other neighboring nodes. In this way, a new client gains connections to a random subset of nodes on the network. The membership management protocol further includes a protocol for reassigning neighboring relationships between nodes when an active node leaves the network. Furthermore, the membership management protocol allows nodes to periodically re-subscribe to the network in order to rebalance the network graph.