We propose a general formal model of isolated hierarchical parallel
computations, and identify several fragments to match the concurrency
constructs present in real-world programming languages such as Cilk
and X10. By associating fundamental formal models (vector addition
systems with recursive transitions) to each fragment, we provide a
common platform for exposing the relative difficulties of algorithmic
reasoning. For each case we measure the complexity of deciding
state-reachability for finite-data recursive programs, and propose
algorithms for the decidable cases. The complexities which include
PTIME, NP, EXPSPACE, and 2EXPTIME contrast with undecidable
state-reachability for recursive multi-threaded programs.