The Web service technology allows the dynamic composition of a workflow (or a business flow) by composing a set of existing Web services scattered across the Internet. While a given Web service may have multiple service instances taking part in several workflows simultaneously, a workflow often involves a set of service instances that belong to different Web services. In order to establish trust relationships amongst service instances, new security protocols are urgently needed. Hada and Maruyabma [3] presented a session-oriented, multi-party authentication protocol to resolve this problem. Within a session their protocol provides a commonly shared session secret for all the service instances, thereby distinguishing the instances from those of other sessions. However, individual instances cannot be distinguished and identified using the session secret. This leads to vulnerable session management and poor threat containment. In this paper we present a new protocol design for multi-party authentication in which each service instance of a given session is provided with a unique identifier. The Coordinated Atomic Action scheme is exploited for achieving an improved level of threat containment. We evaluate the scalability of our design by means of both experiments and an analytical model. The result shows that time consumed by the authentication process increases linearly with an increase in the number of session participants.