I think the time stamp is more important for matching devices. In fact, theoretically, with an accurate enough time stamp you wouldn't need a location to match

I think the time stamp is more important for matching devices. In fact, theoretically, with an accurate enough time stamp you wouldn't need a location to match the devices virtually all the time. Another idea I had would be to tell the users to knock the devices together twice. That way, you would have another dimension for matching devices: the interval between the knocks should be the same, and that doesn't depend on the clocks being synchronized on the two devices.