  We study the problem of parametric parallel complexity analysis of
concurrent, message-passing programs. To make the analysis local and
compositional, it is based on a conservative extension of binary session types,
which structure the type and direction of communication between processes and
stand in a Curry-Howard correspondence with intuitionistic linear logic. The
main innovation is to enrich session types with the temporal modalities next
($\bigcirc A$), always ($\Box A$), and eventually ($\Diamond A$), to
additionally prescribe the timing of the exchanged messages in a way that is
precise yet flexible. The resulting temporal session types uniformly express
properties such as the message rate of a stream, the latency of a pipeline, the
response time of a concurrent queue, or the span of a fork/join parallel
program. The analysis is parametric in the cost model and the presentation
focuses on communication cost as a concrete example. The soundness of the
analysis is established by proofs of progress and type preservation using a
timed multiset rewriting semantics. Representative examples illustrate the
scope and usability of the approach.
