↓Skip to main content

Resource Control for Synchronous Cooperative Threads

Complexity Resource Control
Table of Contents

Roberto M. Amadio, Silvano Dal Zilio
In CONCUR 2004 — 15th International Conference on Concurrency Theory, aug 2004.

conference paper

 PDF  DOI〈10.1016/j.tcs.2006.01.017〉

Abstract
#

We develop new methods to statically bound the resources needed for the execution of systems of concurrent, interactive threads. Our study is concerned with a synchronous model of interaction based on cooperative threads whose execution proceeds in synchronous rounds called instants. Our contribution is a system of compositional static analyses to guarantee that each instant terminates and to bound the size of the values computed by the system as a function of the size of its parameters at the beginning of the instant.

Our method generalises an approach designed for first-order functional languages that relies on a combination of standard termination techniques for term rewriting systems and an analysis of the size of the computed values based on the notion of quasi-interpretation. These two methods can be combined to obtain an explicit polynomial bound on the resources needed for the execution of the system during an instant.

References
#

  • An extended version of this paper appears as Research Report 22-2004, LIF, May 2004.  PDF

  • An abridged version appears in Theoretical Computer Science 358(2-3):229-254, August 2006.  Link

Citation
#


@InProceedings{DalzilioS:rcsct,
   author    = {Amadio, Roberto M. and {Dal Zilio}, Silvano},
   title     = {{Resource Control for Synchronous Cooperative Threads}},
   booktitle = {CONCUR 2004 -- 15th International Conference on Concurrency Theory},
   series    = {Lecture Notes in Computer Science},
   volume    = {3170},
   publisher = {Springer-Verlag},
   doi = {10.1016/j.tcs.2006.01.017},
   pages     = {68--82},
   month     = aug, 
   year      = 2004
}