Add awaiting external dependency predicate

cc @myronmarston 
Actually, there is a useful optimization here...you can avoid calling redis if the appropriate `dependency_is_` flag is already set.