From my cursory inspection, Algorithm::Dependency didn't seem to buy me much over Graph. I'd still be handling the execution and the graph building (or using the format of A::D::Source::File). Maybe I should have a second look, since you think it may be useful.

"Age/change state" can be checked with ordinary date modules or functions. Do you need something else?

The only unusual requirement here is that I should be able to source the date from a database instead of simply from a file's age. Another option in build systems is comparing md5 hashes for changes, but I haven't needed that myself.

My dependency graphs have all been quite small an simple. Fewer than 20 nodes, just managing task order and execution.