A device implementing a system for notifying a first device of availability of a service on a second device includes a processor configured to receive, from the first device of a first user, a first request with respect to whether a service is available on the second device of a second user, and to determine that the service is not available on the second device. The processor is further configured to send, to the first device and in response to the determination, an indication that the service is not available on the second device and an indication of a minimum amount of time before the first device can submit a second request with respect to whether the service is available on the second device. The minimum amount of time is based at least partially on an amount of time that has elapsed since the service was made available to the devices.