Progress as Compositional Lock-Freedom

Abstract : A session-based process satisfies the progress property if its sessions never get stuck when it is executed in an adequate context. Previous work studied how to define progress by introducing the notion of catalysers, execution contexts generated from the type of a process. In this paper, we refine such definition to capture a more intuitive notion of context adequacy for checking progress. Interestingly, our new catalysers lead to a novel characterisation of progress in terms of the standard notion of lock-freedom. Guided by this discovery, we also develop a conservative extension of catalysers that does not depend on types, generalising the notion of progress to untyped session-based processes. We combine our results with existing techniques for lock-freedom, obtaining a new methodology for proving progress. Our methodology captures new processes wrt previous progress analysis based on session types.
Type de document :
Communication dans un congrès
David Hutchison; Takeo Kanade; Bernhard Steffen; Demetri Terzopoulos; Doug Tygar; Gerhard Weikum; Eva Kühn; Rosario Pugliese; Josef Kittler; Jon M. Kleinberg; Alfred Kobsa; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan. 16th International Conference on Coordination Models and Languages (COORDINATION), Jun 2014, Berlin, Germany. Springer, Lecture Notes in Computer Science, LNCS-8459, pp.49-64, 2014, Coordination Models and Languages. 〈10.1007/978-3-662-43376-8_4〉
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-01290067
Contributeur : Hal Ifip <>
Soumis le : jeudi 17 mars 2016 - 15:24:40
Dernière modification le : jeudi 12 mai 2016 - 10:48:04
Document(s) archivé(s) le : samedi 18 juin 2016 - 11:58:58

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Marco Carbone, Ornela Dardha, Fabrizio Montesi. Progress as Compositional Lock-Freedom. David Hutchison; Takeo Kanade; Bernhard Steffen; Demetri Terzopoulos; Doug Tygar; Gerhard Weikum; Eva Kühn; Rosario Pugliese; Josef Kittler; Jon M. Kleinberg; Alfred Kobsa; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan. 16th International Conference on Coordination Models and Languages (COORDINATION), Jun 2014, Berlin, Germany. Springer, Lecture Notes in Computer Science, LNCS-8459, pp.49-64, 2014, Coordination Models and Languages. 〈10.1007/978-3-662-43376-8_4〉. 〈hal-01290067〉

Partager

Métriques

Consultations de la notice

52

Téléchargements de fichiers

13