I'd like to know how PNRP manages to detect other peers in the Global cloud (which I assume is over the internet). I've read it uses "an architecture similar to distributed hash table systems", but that doesn't really tell me much.
It seems to me that at some point, my node has to send some sort of message to somewhere that eventually returns any other peer addresses the algorithm finds, but where does it send this initial message to if there's no central server to ask and it's not aware of any other nodes at this point?
If you are asking only about Global PNRP cloud then perhaps you can find useful the following phrase from "1.3.3.1 Discovering a Cloud" of PNRP protocol specification:
... To discover some nodes in the Global PNRP cloud, the discovering node contacts one of two well-known seed servers whose addresses are resolved via a Domain Name System (DNS) lookup ...
But I think you probably would like to read the full text and follow the links:
To discover nodes on the same link, a node uses the Simple Service Discovery Protocol (SSDP) (as specified in [UPNPARCH1], section 1) to discover other nearby nodes that are already in the cloud. If there are no other nodes in the cloud of interest that exist on the node's link, then the discovering node uses a seed server to find some. To discover some nodes in the Global PNRP cloud, the discovering node contacts one of two well-known seed servers whose addresses are resolved via a Domain Name System (DNS) lookup. To discover some nodes in a Site cloud, the discovering node must know the name or address of a seed server via some other method (for example, manual configuration, or supplied by an application).