Authentication is a key requirement in the establishment of secure interactions between network entities. Several authentication and key establishment protocols have been proposed in recent years. Most of these protocols were designed for an intra-domain environment (i.e. one where the communicating parties reside in a single domain) and then extrapolated to the inter-domain environment. In this paper, the design of inter-domain protocols is investigated. We present the different design choices that need to be carefully considered when designing inter-domain protocols in large distributed systems. We propose three different inter-domain protocols with varying degrees of responsibility placed on the client and the trusted servers. In each case, the assumptions made in the design are explicitly stated. This helps to illustrate the rationale behind the choices made. The proposed protocols use symmetric key systems and are based on Kerberos. The arguments, rationales and designs presented in this paper are also applicable to OSF's Distributed Computing Environment (DCE).