Causal dataflow analysis for concurrent programs

Azadeh Farzan; P. Madhusudan

doi:10.1007/978-3-540-71209-1_10

Causal dataflow analysis for concurrent programs

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Tools 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
Editors	Orna Grumberg, Michael Huth
Publisher	Springer
Pages	102-116
Number of pages	15
ISBN (Electronic)	9783540712091
ISBN (Print)	9783540712084
DOIs	https://doi.org/10.1007/978-3-540-71209-1_10
State	Published - 2007
Event	13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, (TACAS 2007) - Braga, Portugal Duration: Mar 24 2007 → Apr 1 2007

Publication series

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

Conference

Conference	13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, (TACAS 2007)
Country/Territory	Portugal
City	Braga
Period	3/24/07 → 4/1/07

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-540-71209-1_10

Library availability

Discover UIUC Full Text

Cite this

Farzan, A., & Madhusudan, P. (2007). Causal dataflow analysis for concurrent programs. In O. Grumberg, & M. Huth (Eds.), Tools 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 (pp. 102-116). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4424 LNCS). Springer. https://doi.org/10.1007/978-3-540-71209-1_10

Causal dataflow analysis for concurrent programs. / Farzan, Azadeh; Madhusudan, P.
Tools 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. ed. / Orna Grumberg; Michael Huth. Springer, 2007. p. 102-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4424 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Farzan, A & Madhusudan, P 2007, Causal dataflow analysis for concurrent programs. in O Grumberg & M Huth (eds), Tools 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4424 LNCS, Springer, pp. 102-116, 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, (TACAS 2007), Braga, Portugal, 3/24/07. https://doi.org/10.1007/978-3-540-71209-1_10

Farzan A, Madhusudan P. Causal dataflow analysis for concurrent programs. In Grumberg O, Huth M, editors, Tools 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. Springer. 2007. p. 102-116. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-71209-1_10

Farzan, Azadeh ; Madhusudan, P. / Causal dataflow analysis for concurrent programs. Tools 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. editor / Orna Grumberg ; Michael Huth. Springer, 2007. pp. 102-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{637adf35ae1647bfa00e0bfedc8c291c,

title = "Causal dataflow analysis for concurrent programs",

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.",

author = "Azadeh Farzan and P. Madhusudan",

year = "2007",

doi = "10.1007/978-3-540-71209-1_10",

language = "English (US)",

isbn = "9783540712084",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "102--116",

editor = "Orna Grumberg and Michael Huth",

booktitle = "Tools 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",

address = "Germany",

note = "13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, (TACAS 2007) ; Conference date: 24-03-2007 Through 01-04-2007",

}

TY - GEN

T1 - Causal dataflow analysis for concurrent programs

AU - Farzan, Azadeh

AU - Madhusudan, P.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=37149001047&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=37149001047&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-71209-1_10

DO - 10.1007/978-3-540-71209-1_10

M3 - Conference contribution

AN - SCOPUS:37149001047

SN - 9783540712084

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 102

EP - 116

BT - Tools 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

A2 - Grumberg, Orna

A2 - Huth, Michael

PB - Springer

T2 - 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, (TACAS 2007)

Y2 - 24 March 2007 through 1 April 2007

ER -

Causal dataflow analysis for concurrent programs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this