According to the code in SaslAuthProvider::RunKinit(), before acquiring a new key, we sleep for the following amount of time:
max(keberos_reinit_interval - random(0 to 5 minutes), 60) seconds
Looking at the logs from a secure cluster run, we observed that every impalad slept for the same amount of time which means that the pseudo-randomization code doesn't really achieve pseudo-randomness.
We suspect that it's because the generator is not seeded during creation.
The whole point of adding the pseudo-randomization factor was to avoid impalad's from storming the KDC for a new ticket at the same time. So, this could have caused some of the earlier "Cannot contact any KDC for realm 'xyz'" errors. But it's hard to tell as it's not an easily reproducible error.
Need to confirm on a secure cluster. Will post an update once I do.