An auto-discovery system discovers related components of a service operating on a distributed network. This auto-discovery system involves (1) selecting a model of the configuration of the service; (2) determining, from the model, “scope hints” that limit the possible locations of related components; (3) determining a root component of the service; (4) using scope hints to limit the search, to rapidly find related instances of components contained in the root service component; (5) determining whether a quorum of components comprising a distributed service has been discovered; (6) determining the parent service component of each discovered service component by instance matching; and (7) using the instance match information to determine the discovery tree of components that have the structure of the service map, share a common root component, and define a service group. This auto-discovery system efficiently discovers the components of a wide range of services within a distributed environment. The system limits the scope of searches for components related to previously discovered components. The system determines the relationships between the discovered service components, and matches them into groups of related services. This enables an operational manager of a distributed service to better determine service configurations, expand resource bottlenecks, and improve an end-users' experience.