Various embodiments of message gate pairs are described. A message gate pair may provide a mechanism for communicating requests from clients to services and response from services to clients. A message gate pair may be used to create a secure atomic bi-directional message channel for request-response message passing. The distributed computing environment may employ a message transport in which a message gate exists on both the client and the service. The two gates may work together to provide a secure and reliable message channel. Client and service gates may perform the actual sending and receiving of the messages from the client to the service using a protocol specified in a service advertisement. The message gates may provide a level of abstraction between a client and a service. A client may reference a service through a message gate instead of referencing the service directly. Messages gates may allow clients and services to exchange messages in a secure and reliable fashion over any suitable message transport (e.g. HTTP). For a client, a message gate may represent the authority to use some or all of a service's capabilities. Each capability may be expressed in terms of a message that may be sent to the service. Each such message may be sent through a client message gate that may verify the correctness of the message. The message may be received by a service message gate that may authenticate the message and verify its correctness.