[gnulinux]

Can one not just note the timestamp of last change with a monotonic clock. Then, dependencies check the timestamp of last computation, and pessimistically determine if recomputation is needed.

Seems like the trouble here is you'll have to traverse the tree every time to check timestamps but if the dependency is dirty that needs to happen anyway.

[naasking]

That's effectively a pull-based system, which works fine but is inefficient. With a binary dependency tree of depth N, you have to touch 2^N nodes in such a pull-based system every time you evaluate it, no matter how many nodes you may have updated.

If you only updated 1 node, a push-based system will only update nodes that have changed, which will be considerably less (likely linear in depth). For instance, consider:

    var evenSeconds = clock.Seconds.Where(x => x % 2 == 0);
    var countEvents = evenSeconds.Count();
    var minutes = clock.Seconds.Count(x => x / 60);
    var hours = minutes.Count(x => x / 60);

Even though evenSeconds and countEvents is only updated every other second, and minutes once every 60 seconds, your pull-based approach will have to check all nodes up to the root every time clock.Seconds changes.

In a push-based system, clock.Seconds would trigger seconds+1. If that's not even, propagation stops there, if it is even then this updates evenSeconds, which would then trigger an update for countEvents. Ditto logic for minutes and hours.

You can see the push-based system permits minimal state changes via early termination if downstream dependents won't see any changes.