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 a direct connection is infeasible, or an attempted direct connection 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. The invitation service can perform its functions without maintaining per-connection state information for the mobile devices.