A distributed system in which time-dependent credentials are supplied by controllers that operate according to different local times. Errors that might arise from the controllers generating inconsistent credentials because of time skew are avoided by identifying credentials generated during transition intervals in which different ones of the controllers may generate different credentials at the same absolute time. During a transition interval, controllers and other devices may use credentials differentially based on the nature of the authentication function. Each controller may periodically renew its credentials based on self-scheduled renewals or based on requests from other devices, such that renewal times are offset by random delays to avoid excessive network traffic. Controllers may determine which credential is valid for any given time, based on a cryptographically secure key associated with that time and information identifying the entity that is associated with that credential.