In this paper we propose an extension of the Service Oriented Architecture that supports discovery of Web services across organization boundaries. We provide a detailed discussion of both the architectural and implementation considerations, and we provide an empirical evaluation that shows that indeed our prototype implementation scales with both the number of Web services and the number of organizations involved.