Hierarchical Directories were introduced to provide Service Address Routing (Scherson, Valencia in: Proceedings of the international symposium on parallel architectures, algorithms and networks (I-SPAN), Las Vegas, USA, 2005) embedded in a class of Hierarchical Interconnection Networks known as Least Common Ancestor Networks (LCANs). The algorithms for service discovery in SAR are shown to extend to the GRID when the LCAN is effectively mapped onto the loosely coupled Internet connected computing cluster. In SAR, nodes (programs) communicate by invoking services from the network itself. It is the network-embedded service discovery and addressing mechanism that provides the physical binding. Even though the SAR concept was conceived for tightly coupled interconnection networks, it can also be applied to an Internet GRID system by mapping the SAR network directory (considered to be LCAN-embedded) onto the loosely coupled GRID. Once the network is successfully mapped to the subjacent network, all scalability, fault-tolerance, functionality, and every other advantage of an LCAN-SAR system are automatically available in the resulting implementation. We present a novel way to perform a completely distributed and dynamic service discovery that not only performs faster lookups by avoiding well known bottlenecks in centralized systems, but has inherent fault tolerance mechanisms.