Well, Gnutella can do service discovery.
What it can do well are fuzzy searches with many results. Scaling should mostly be O(log(N)), thanks to Dynamic Querying and the Query Routing Protocol (which turns the original pure broadcast model of Gnutelly 0.4 into a very efficient directed search in Gnutella 0.6).
What it can do very well is discovering additional sources of a found service. See the download mesh.
The initial connection in Gnutella actually is service discovery. See UDP Host Caches.
What it cannot do that well are exact searches (more exactly: for exact searches, Gnutella has a DHT - see Mojito. That has guaranteed logarithmic scaling, but can *only* do exact searches efficiently).
Generally see
Gnutella for Users - Gnufu