The Grid has rapidly moved from a toolkit-centered approach, composed of a set of middleware tools, toward a more application-oriented Service Oriented Architecture in which resources are exposed as services. The soaring number of available services advocates distributed and semantic-based discovery architectures. Distribution promotes scalability and fault-tolerance whereas semantics is required to provide for meaningful descriptions of services and support their efficient retrieval. Current approaches exploit either Semantic Overlay Networks (SONs) or Distributed Hash Tables (DHTs) sweetened with some ”semantic sugar”. SONs enable semantic driven query answering but are less scalable than DHTs, which on their turn, feature efficient but semantic-free query answering based on ”exact” matching. This paper presents the ERGOT system combining DHTs and SONs to enable distributed and semantic based service discovery on the Grid. We argue that these two models can benefit from each other in the sense that SONs can be constructed by exploiting DHTs mechanisms thus enlightening the way to the semantics-free content publishing and retrieval mechanisms of the latter. In particular, ERGOT allows establishing semantic links among peers, and the SONs, by scrutinizing semantic service descriptions they advertise on the DHT. As we will show semantic links can also be viewed as semantic shortcuts on the DHT. Finally, ERGOT exploits an ad hoc semantic similarity metric to perform service matchmaking and numerically rank results.