In one embodiment, a parent network device, operating according to a first Trickle operation using a first selected minimum contention interval, responds to detecting a loss of attached child network devices by starting a second Trickle operation using a second selected minimum contention interval. The second Trickle operation includes maintaining the second selected minimum contention interval for subsequent iterations of the second Trickle operation. The parent network device initiates an accelerated transmission rate of the advertisement message that is faster than the first and second Trickle operations (using a third selected minimum contention interval less than the first minimum contention interval) in response to receiving a message from one of the lost child network devices, and resumes the first Trickle operation upon recovery of all the lost child network devices.