View in EDS

Undecidability of asynchronous session subtyping.

Saved in:
Bibliographic Details
Title: Undecidability of asynchronous session subtyping.
Authors: Bravetti, Mario1, Zavattaro, Gianluigi1, Carbone, Marco2
Source: Information & Computation. Oct2017, Vol. 256, p300-320. 21p.
Subjects: Session Initiation Protocol (Computer network protocol), Queuing theory, Computer networks, Asynchronous transfer mode, Computer network protocols
Abstract: Session types are used to describe communication protocols in distributed systems and, as usual in type theories, session subtyping characterizes substitutability of the communicating processes. We investigate the (un)decidability of subtyping for session types in asynchronously communicating systems. We first devise a core undecidable subtyping relation that is obtained by imposing limitations on the structure of types. Then, as a consequence of this initial undecidability result, we show that (differently from what stated or conjectured in the literature) the three notions of asynchronous subtyping defined so far for session types are all undecidable. Namely, we consider the asynchronous session subtyping by Mostrous and Yoshida for binary sessions, the relation by Chen et al. for binary sessions under the assumption that every message emitted is eventually consumed, and the one by Mostrous et al. for multiparty session types. Finally, by showing that two fragments of the core subtyping relation are decidable, we evince that further restrictions on the structure of types make our core subtyping relation decidable. [ABSTRACT FROM AUTHOR]
Copyright of Information & Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 125338293
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Undecidability of asynchronous session subtyping.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bravetti%2C+Mario%22">Bravetti, Mario</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Zavattaro%2C+Gianluigi%22">Zavattaro, Gianluigi</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Carbone%2C+Marco%22">Carbone, Marco</searchLink><relatesTo>2</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Information+%26+Computation%22">Information & Computation</searchLink>. Oct2017, Vol. 256, p300-320. 21p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Session+Initiation+Protocol+%28Computer+network+protocol%29%22">Session Initiation Protocol (Computer network protocol)</searchLink><br /><searchLink fieldCode="DE" term="%22Queuing+theory%22">Queuing theory</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+networks%22">Computer networks</searchLink><br /><searchLink fieldCode="DE" term="%22Asynchronous+transfer+mode%22">Asynchronous transfer mode</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+network+protocols%22">Computer network protocols</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Session types are used to describe communication protocols in distributed systems and, as usual in type theories, session subtyping characterizes substitutability of the communicating processes. We investigate the (un)decidability of subtyping for session types in asynchronously communicating systems. We first devise a core undecidable subtyping relation that is obtained by imposing limitations on the structure of types. Then, as a consequence of this initial undecidability result, we show that (differently from what stated or conjectured in the literature) the three notions of asynchronous subtyping defined so far for session types are all undecidable. Namely, we consider the asynchronous session subtyping by Mostrous and Yoshida for binary sessions, the relation by Chen et al. for binary sessions under the assumption that every message emitted is eventually consumed, and the one by Mostrous et al. for multiparty session types. Finally, by showing that two fragments of the core subtyping relation are decidable, we evince that further restrictions on the structure of types make our core subtyping relation decidable. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Information & Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=125338293
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.ic.2017.07.010
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 21
        StartPage: 300
    Subjects:
      – SubjectFull: Session Initiation Protocol (Computer network protocol)
        Type: general
      – SubjectFull: Queuing theory
        Type: general
      – SubjectFull: Computer networks
        Type: general
      – SubjectFull: Asynchronous transfer mode
        Type: general
      – SubjectFull: Computer network protocols
        Type: general
    Titles:
      – TitleFull: Undecidability of asynchronous session subtyping.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bravetti, Mario
      – PersonEntity:
          Name:
            NameFull: Zavattaro, Gianluigi
      – PersonEntity:
          Name:
            NameFull: Carbone, Marco
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2017
              Type: published
              Y: 2017
          Identifiers:
            – Type: issn-print
              Value: 08905401
          Numbering:
            – Type: volume
              Value: 256
          Titles:
            – TitleFull: Information & Computation
              Type: main
ResultId 1