his paper studies the complexity of
π
-calculus processes with res-
pect to the quantity of transitions caused by an incoming message.
First we propose a typing system for integrating Bellantoni and
Cook’s characterisation of polynomially-bound recursive functions
into Deng and Sangiorgi’s typing system for termination. We then
define computational complexity of distributed messages based on
Degano and Priami’s causal semantics, which identifies the depen-
dency between interleaved transitions. Next we apply a syntactic
flow analysis to typable processes to ensure the computational bound
of distributed messages. We prove that our analysis is
decidable
for
a given process;
sound
in the sense that it guarantees that the total
number of messages causally dependent of an input request received
from the outside is bounded by a polynomial of the content of this
request; and
complete
which means that each polynomial recursive
function can be computed by a typable process.