A first device periodically transmits a first audio signal that encodes a first code over an audio channel that is shared between the first device and a second device, and the second device periodically transmits a second audio signal that encodes a second code over the audio channel. When the first device receives the second audio signal over the audio channel, the first device extracts the second code from the second audio signal and sends the second code to a server. When the second device receives the first audio signal over the audio channel, the second device extracts the first code from the first audio signal and sends the first code to the server. If the server receives the first code from the second device and/or the second code from the first device, the server can conclude that the first device is in proximity to the second device.