Causal dataflow analysis for concurrent programs

Research output: Contribution to journalArticle

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)
Pages (from-to)102-116
Number of pages15
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4424 LNCS
StatePublished - 2007

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this