Policy changes are propagated to access control devices of a distributed system. The policy changes are given immediate effect without having to wait for the changes to propagate through the system. A token encodes the policy change and can be provided in connection with access requests. Before an access control device has received a propagated policy change, the access control device can evaluate a token provided in connection with a request to determine, consistent with the policy change, whether to fulfill the request.