Complexity Information Flow in a Multi-threaded Imperative Language

Jean-Yves Marion 1 Romain Péchoux 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We propose a type system to analyze the time consumed by multi-threaded imperative programs with a shared global memory, which delineates a class of safe multi-threaded programs. We demon-strate that a safe multi-threaded program runs in polynomial time if (i) it is strongly terminating wrt a non-deterministic scheduling policy or (ii) it terminates wrt a deterministic and quiet scheduling policy. As a consequence, we also characterize the set of polynomial time functions. The type system presented is based on the fundamental notion of data tiering, which is central in implicit computational complexity. It regu-lates the information flow in a computation. This aspect is interesting in that the type system bears a resemblance to typed based informa-tion flow analysis and notions of non-interference. As far as we know, this is the first characterization by a type system of polynomial time multi-threaded programs.
Type de document :
Communication dans un congrès
T. V. Gopal; Manindra Agrawal; Angsheng Li; S. Barry Cooper. TAMC 2014, Apr 2014, Chennai, India. Springer, pp.124 - 140, 2014, Theory and Applications of Models of Computation. 〈10.1007/978-3-319-06089-7_9〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01084043
Contributeur : Romain Péchoux <>
Soumis le : mardi 18 novembre 2014 - 13:58:00
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : vendredi 14 avril 2017 - 20:15:17

Fichier

hulotte.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Yves Marion, Romain Péchoux. Complexity Information Flow in a Multi-threaded Imperative Language. T. V. Gopal; Manindra Agrawal; Angsheng Li; S. Barry Cooper. TAMC 2014, Apr 2014, Chennai, India. Springer, pp.124 - 140, 2014, Theory and Applications of Models of Computation. 〈10.1007/978-3-319-06089-7_9〉. 〈hal-01084043〉

Partager

Métriques

Consultations de la notice

180

Téléchargements de fichiers

320