  The dynamic cavity method provides the most efficient way to evaluate
probabilities of dynamic trajectories in systems of stochastic units with
unidirectional sparse interactions. It is closely related to sum-product
algorithms widely used to compute marginal functions from complicated global
functions of many variables, with applications in disordered systems,
combinatorial optimization and computer science. However, the complexity of the
cavity approach grows exponentially with the in-degrees of the interacting
units, which creates a de-facto barrier for the successful analysis of systems
with fat-tailed in-degree distributions. In this manuscript, we present a
dynamic programming algorithm that overcomes this barrier by reducing the
computational complexity in the in-degrees from exponential to quadratic,
whenever couplings are chosen randomly from (or can be approximated in terms
of) discrete, possibly unit-dependent, sets of equidistant values. As a case
study, we analyse the dynamics of a random Boolean network with a fat-tailed
degree distribution and fully asymmetric binary $\pm J$ couplings, and we use
the power of the algorithm to unlock the noise dependent heterogeneity of
stationary node activation patterns in such a system.
