An apparatus, method, and machine-readable medium are described for establishing peer-to-peer ("P2P") communication channels. In particular, in one embodiment, an invitation service performs a series of transactions to enable P2P communication between two or more mobile data processing devices. Prior to attempting to establish a P2P network communication channel, the invitation service may first collect network information for each of the mobile devices and use the network information to determine if a direct P2P network communication channel is feasible. If a direct connection is feasible, then the invitation service provides for direct P2P communication, pushing the necessary network information to each of the mobile devices. If, however, a direct connection is infeasible or if a direct connection is attempted and fails, then the invitation service may identify network information associated with a relay service. The network information may then be used by any pair of mobile devices to establish a connection through the relay service. In addition, in one embodiment, the invitation service can perform its functions without maintaining any per-connection state information for any of the mobile devices.