Worst-case blocking scenarios for distributed real-time programs

For detecting timing errors in distributed real-time programs it is essential to know all combinations of execution paths of subprograms t₀,t₁,...,t_n where a given path of t _o experiences a worst-case blocking time caused by a scenario of operations on execution paths of t₁,...,t_n, due to such operations blocking certain operations of t_o while accessing shared resources. This paper deals with the problem of determining all possible worst-case blocking scenarios of an execution path of t_o by execution paths of t₁,...,t_n . While this problem is NP-hard we give a polynomial algorithm for an associated (reduced) problem which computes an often tight superset of these scenarios in a variety of practically relevant application situations