Systems and methods are provided for efficiently managing a cache in a distributed environment. When entries are written into a cache, the entries include dependency information. The distributed system keeps invalidation entries that keep track of what dependent values have change and enforces invalidation of entries on cache reads. An asynchronous process actively invalidates entries and garbage collects the invalidation entries. The distributed system advantageously allows writing and reading cached entries across service boundaries.