The description of the service is a little confusing. The text says you want a service that knows about dependencies, but the interface expects the caller to provide them. There would presumably some kind of updater daemon that calls popDirty periodically, but then the dependencies of the popped URLs also need to be updated -is that the responsibility of the caller (in which case how does it know what they are?) or the service (in which case how does it know when the update is finished and a the resource safe to use?)?
I get the feeling multiple concepts are mixed together here. The responsibility of a depencency tracking service is to track dependencies and provide information about them. It would have interface methods for declaring / removing resources, declaring / removing dependencies between them, maybe adding callbacks for dynamically evaluated dependencies, and fetching the dependencies of a specific resource. (And probably track cache expiry times as that's pretty closely related to the dependency graph.) Actually traversing the graph should be done by a different class (which probably has no reason to be a service). Also as @Pchelolo says there is the question of push vs. pull, and there is no reason for the service to know anything about that.