Causal dataflow analysis for concurrent programs

Azadeh Farzan, P. Madhusudan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We define a novel formulation of dataflow analysis for concurrent programs, where the flow of facts is along the causal dependencies of events. We capture the control flow of concurrent programs using a Petri net (called the control net), develop algorithms based on partiallyordered unfoldings, and report experimental results for solving causal dataflow analysis problems. For the subclass of distributive problems, we prove that complexity of checking data flow is linear in the number of facts and in the unfolding of the control net.

Original languageEnglish (US)
Title of host publicationTools and Algorithms for the Construction and Analysis of Systems - 13th International Conference, TACAS 2007. Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007
EditorsOrna Grumberg, Michael Huth
PublisherSpringer-Verlag Berlin Heidelberg
Pages102-116
Number of pages15
ISBN (Electronic)9783540712091
ISBN (Print)9783540712084
DOIs
StatePublished - 2007
Event13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, (TACAS 2007) - Braga, Portugal
Duration: Mar 24 2007Apr 1 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4424 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, (TACAS 2007)
CountryPortugal
CityBraga
Period3/24/074/1/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Causal dataflow analysis for concurrent programs'. Together they form a unique fingerprint.

Cite this