uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Verification of Asynchronous Programs with Nested Locks
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
LIAFA, CNRS and University of Paris Diderot. (Modeling and Verification)
Chennai Mathematical Institute, Chennai, India.
TU Braunschweig, Germany.
2017 (English)In: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India / [ed] Satya Lokam and R. Ramanujam, Dagstuhl, Germany, 2017, Vol. 93, 11:1-11:14 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we consider asynchronous programs consisting of multiple recursive threads running in parallel. Each of the threads is equipped with a multi-set. The threads can create tasks and post them onto the multi-sets or read a task from their own. In addition, they can synchronise through a finite set of locks. In this paper, we show that the reachability problem for such class of asynchronous programs is undecidable even under the nested locking policy. We then show that the reachability problem becomes decidable (Exp-space-complete) when the locks are not allowed to be held across tasks. Finally, we show that the problem is NP-complete when in addition to previous restrictions, threads always read tasks from the same state.

Place, publisher, year, edition, pages
Dagstuhl, Germany, 2017. Vol. 93, 11:1-11:14 p.
Series
Leibniz International Proceedings in Informatics (LIPIcs), 93
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:uu:diva-337133OAI: oai:DiVA.org:uu-337133DiVA: diva2:1168358
Conference
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017
Projects
UPMARC
Available from: 2017-12-20 Created: 2017-12-20 Last updated: 2017-12-20

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Atig, Mohamed Faouzi
By organisation
Computer Systems
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 15 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf