The present invention relates to methods and arrangements for locating services in a structured peer-to-peer distributed hash table, DHT, based, overlay communication network (310). The invention comprises two inter-related methods and nodes. The first method is used by a service node (321) to “advertise” to the overlay network (310) that it is providing a particular service (S1). This is done by distributing instances (351,352,353) of a service object (O1) that are stored in different nodes (331,332,333) in the overlay network (310) and where the instances (351,352,353) comprise an address to the service node (321). The other method is to locate at least one of these instances (351,352,353) with a predetermined probability and with a predetermined number of location request messages (390) from a user node (311) wishing to use the particular service (S1).