Future commercial software systems will be based on distributed service oriented architectures in which applications are composed dynamically from remote components. A key part of service-oriented computing is the ability for clients to discover remote services that fulfill specific requirements. Since the mid-1990s, various commercial and public domain designs for service discovery systems have been proposed that enable clients and services to rendezvous in a distributed system. The report characterizes such designs as first-generation service discovery systems, based on the belief that experience with these systems will lead to future, improved designs. Using three widely used service discovery systems as a basis, this publication first presents a high level overview of the operation of service discovery protocols. A detailed generic model of first-generation service discovery systems, written in UML, follows this. The UML model provides an in-depth analysis of the alternative service discovery designs available today, including the major functional components that comprise these designs, the behaviors of these components, and the information they exchange. The report verifies the generality of the model by mapping its component element to corresponding elements of existent and emerging service discovery systems. This report also identifies issues that designers should attempt to resolve in the next generation of service discovery systems. The analysis is then extended to provide designers of future service discovery systems with a means to evaluate designs. First, the report proposes a set of service goals that service discovery systems should strive to satisfy to ensure a desirable level of quality of service. These goals provide a basis to define metrics, for evaluation the behavior and measuring performance of system designs and implementations. Second, the report identifies potential performance issues that may arise during operation of service discovery systems. Identifying performance issues can alert designers and implementers to the potential for unexpected behavior when service discovery technology is deployed at large scale. The report presents possible solutions to performance problems that extend well-known optimization algorithms for distributed systems and present new algorithms tailored to service discovery environments. The contributions in this report will help to improve the quality of the next generation of service discovery systems on which the service-oriented architectures of tomorrow appear likely to depend. Further, should an industry standards group choose to develop a unified specification for service discovery, the model should provide helpful input to the process.