  Neighbor discovery is the procedure using which two wireless devices initiate
a first contact. In low power ad-hoc networks, radios are duty-cycled and the
latency until a packet meets a reception phase of another device is determined
by a random process. Most research considers slotted protocols, in which the
points in time for reception are temporally coupled to beacon transmissions. In
contrast, many recent protocols, such as ANT/ANT+ and Bluetooth Low Energy
(BLE) use a slotless, periodic-interval based scheme for neighbor discovery.
Here, one device periodically broadcasts packets, whereas the other device
periodically listens to the channel. Both periods are independent from each
other and drawn over continuous time. Such protocols provide 3 degrees of
freedom (viz., the intervals for advertising and scanning and the duration of
each scan phase). Though billions of existing BLE devices rely on these
protocols, neither their expected latencies nor beneficial configurations with
good latency-duty-cycle relations are known. Parametrizations for the
participating devices are usually determined based on a "good guess". In this
paper, we for the first time present a mathematical theory which can compute
the neighbor discovery latencies for all possible parametrizations. Further,
our theory shows that upper bounds on the latency can be guaranteed for all
parametrizations, except for a finite number of singularities. Therefore,
slotless, periodic interval-based protocols can be used in applications with
deterministic latency demands, which have been reserved for slotted protocols
until now. Our proposed theory can be used for analyzing the neighbor discovery
latencies, for tweaking protocol parameters and for developing new protocols.
