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 demonstrate 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 regulates the information flow in a computation. This aspect is interesting in that the type system bears a resemblance to typed based information 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 :
Rapport
[Research Report] 2012, pp.16
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-00684026
Contributeur : Romain Péchoux <>
Soumis le : vendredi 30 mars 2012 - 13:59:44
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 18:59:04

Fichiers

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

Identifiants

  • HAL Id : hal-00684026, version 1
  • ARXIV : 1203.6878

Collections

Citation

Jean-Yves Marion, Romain Péchoux. Complexity Information Flow in a Multi-threaded Imperative Language. [Research Report] 2012, pp.16. 〈hal-00684026〉

Partager

Métriques

Consultations de la notice

375

Téléchargements de fichiers

226