  Dynamic networks of concurrent pushdown systems (DCPS) are a theoretical
model for multi-threaded recursive programs with shared global state and
dynamical creation of threads. The (global) state reachability problem for DCPS
is undecidable in general, but Atig et al. (2009) showed that it becomes
decidable, and is in 2EXPSPACE, when each thread is restricted to a fixed
number of context switches. The best known lower bound for the problem is
EXPSPACE-hard and this lower bound follows already when each thread is a
finite-state machine and runs atomically to completion (i.e., does not switch
contexts). In this paper, we close the gap by showing that state reachability
is 2EXPSPACE-hard already with only one context switch. Interestingly, state
reachability analysis is in EXPSPACE both for pushdown threads without context
switches as well as for finite-state threads with arbitrary context switches.
Thus, recursive threads together with a single context switch provide an
exponential advantage.
  Our proof techniques are of independent interest for 2EXPSPACE-hardness
results. We introduce transducer-defined Petri nets, a succinct representation
for Petri nets, and show coverability is 2EXPSPACE-hard for this model. To show
2EXPSPACE-hardness, we present a modified version of Lipton's simulation of
counter machines by Petri nets, where the net programs can make explicit
recursive procedure calls up to a bounded depth.
