article

Free access

Modeling concurrency in parallel debugging

Authors:

G. E. KaiserAuthors Info & Claims

ACM SIGPLAN Notices, Volume 25, Issue 3

Pages 11 - 20

https://doi.org/10.1145/99164.99166

Published: 01 February 1990 Publication History

Abstract

We propose a debugging language, Data Path Expressions (DPEs), for modeling the behavior of parallel programs. The debugging paradigm is for the programmer to describe the expected program behavior and for the debugger to compare the actual program behavior during execution to detect program errors. We classify DPEs into five subclasses according to syntactic criteria, and characterize their semantics in terms of a hierarchy of extended Petri Net models. The characterization demonstrates the power of DPEs for modeling parallelism. We present predecessor automata as a mechanism for implementing the third subclass of DPEs, which expresses bounded parallelism. Predecessor automata extend finite state automata to provide efficient event recognizers for parallel debugging. We briefly describe the application of DPEs to race conditions, deadlock and starvation.

References

[1]

T.S. Balraj and M.J. Foster. Miss Manners: A Specialized Silicon Compiler for Synchronizers. In Proceedings of the Fourth MIT Conference, pages 3-20. The MIT Press, April, 1986.

Digital Library

[2]

Peter Bates and Jack C. Wileden. An Approach to High-Level Debugging of Distributed System. In A CM SIGSoftlSIGP lan Software Engineering Symposium on High.Level Debugging, pages 107-111. Pacific Grove, CA, March, 1983. Special issue of Software Engineering Notes, 8(4), August I983.

Digital Library

[3]

Peter C. Bates. Shuffle Automata: A Formal Model for Behavior Recognition in Distributed Systems. Technical Report COINS 87-27, University of Massachusetts at Amherst, January, 1987.

Digital Library

[4]

Peter Bates. Distributed Debugging Tools for Heterogeneous Distributed Systems. In 8th lnternational Conference on Distributed Computing Systems, pages 308-315. Computer Society Press. San Jose CA, June, 1988.

[5]

Peter Bates. Distributed Debugging Tools for Heterogeneous Distributed Systems. In ACM SIGPLAN/SIC, Op# Work.chop oA Parall#1 and Distril#lcd Debugging, pages 11-22. Madison WI, May, 1988. Spocial issue of SIGPLANNotices, 24(1 ), January 1989.

Digital Library

[6]

Bemd Bruegg~ and Peter Hibbard. Generalized Path Expressions: A High-Level Debugging Mechanism. The Journal of Systems and Software 2(3):265-Z'/6, 1983.

[7]

Bemd Bruegge. Adaptability and Portability of Symbolic Debuggers. PhD thesis, Carnegie Mellon University, 1985. CMU-CS-85-174.

Digital Library

[8]

R.H. Campbell and A.N. Habermann. The Specification of Process Synchronization by Path Expressions. In G. Goos and J. Hartmanis (editors), Lecture Notes in Computer Science. Volume 16: Operating Systems, pages 89-102. Springer-Verlag, Berlin, 1974.

[9]

E.G. Coffman, Jr., M. Elphick; and A. Shoshani. Systems Deadlocks. Computing Surveys 3(2):71-76, June, 1971.

Digital Library

[10]

M.J. Foster. Avoiding Latch Formation in Regular Language Recognizers. In Proceedings of the A ilerton Conference on Communication, Control, and Computing, pages 740-748. University of ILlinois, Urbana-Champaign IL, October, 1986. This paper also appears in the IEEE VLSI Technical Bulletin, 1 (2), September 1986.

[11]

Vijay Kumar Garg. Specification and Analysis of Distributed Systems With a Large Number of Processes. PhD thesis, University of California at Berkeley, 1988.

[12]

German S. Goldszrnidt, Shmuel Katz and Shaula Yemini. High Level Language Debugging for Concurrent Programs. Technical Report RC14341, IBM Research Division, T.J.Watson Research Center, Yonktown Heights, N.Y. 10598, January, 1989.

[13]

M. Hack. Decidability Questions for Petri Nets. PhD thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, 1975. Technical Report 161.

Digital Library

[14]

John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Ctnnpany, 1979, pages 28-35.

Digital Library

[15]

William E. Howden. Software Engineering and Technology: Functional Program Testing & Analysis. McGraw-Hilt Book Co., New York, 1987.

Digital Library

[16]

Wenwey Hseush and GaLl E. Kaiser. Data Path Debugging: Dam-Oriented Debugging for a Concurrent Programming Language. In ACM SIGPLANISIGOps Workshop on Parallel and Distributed Debugging, pages 236-246. Madison W'I, May, 1988. Special issue of SIGPLAN Notices, 24(1), January 1989.

Digital Library

[17]

Wenwey I4seush and GaLl E. KAISER. Modeling Concurrency in Parallel Debugging. Technical Report cues460, Computer Science Department, Columbia University, NY, NY, October, 1989.

[18]

S.C. Johnscm and M.E. Lesk. Language Development Tools. The Bell System Technical Journal 57(6):2155-2175, July-Augast, 1978.

[19]

Gaff E. Kaiser, Steven S. Popovieh, Wenwey Hseush and Shyhtsun Felix Wu. Melding Multiple Granularities of Parallelism. In Stephen Cook (editor), 3rd European Conference on Object- Oriented Programming, pages 147-166. Cambridge University Press, Nottingham, UK, July, 1989.

[20]

R. Keller. Vector Replacement Systems: A Formalism for Modeling Asynchronous Systems. Te#.hnieai Report I 17, C#nputer Science Laboratory, Princeton University, December, }972.

[21]

Donald E. Knuth. Semantics of Context-Free Languages. Mathematical Systems Theory 2(2):127-145, June, 1968.

[22]

Lealie Lamport. Time, Clocks and the Ordering of Events in a Distributed System. CACM 21(7):558-564, Jaly, 1978.

Digital Library

[23]

P.E. Lauer and R. H. Campbell. Formal Semantics of a Class of High-Level Primitives for Coordinating Concurreaat Processes. Acta lnformatica 5(4):297-332, 1975.

[24]

P.E. Lauer and M. W. Shields. Formal behavioural specification of coneurremt systems without globality assumptions. In J. Diaz and l.Ramos (editor), Lecture Notes in Computer Science. Number 107: Proceedings of lnternation Colloquium on Formalization of Programming Concepts, pages 115-151. Springer-Verlag, Berlin, 1981.

[25]

M. Linton. A Debugger for the Berkeley Pascal System. Master's thesis, University of California at B erkeley, June, 198 I.

[26]

Barton P. Miller and Jong-Deok Choi,. Breakpoints and Halting in Distributed Programs. In 8th International Conference on Distributed Computing Systems, pages 316-323. Computer Society Press, San Jose CA, June, 1988.

[27]

Robin Milner. A Calculus of Communicating S ystems. in G. Goos and J. Hartmanis (editors),Lecture Notes in Computer Science (92). Springer-Verlag, Berlin, 1980.

Digital Library

[28]

James L. Peterson. Pad Net Theory and The Modeling of Systerna. Prentice-Hall, Inc., Englewood Cliffs, NJ 07632, 1981.

Digital Library

[29]

Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baron, David Black, William Bolosky and Jonathan Chew. Machine-lndependent Virtual Memory Management for Paged Uaiprocessor and Muttiproeessor Architectures. In 2rid International Conference on Architectural Support for Programming Languages and Operating Systems, pages 31-39. Palo Alto CA, October, 1987. Special issue of SlGPlan Notices, 22(10), October 1987.

Digital Library

[30]

Thoma# Reps. Generating Language-Based Environments. The MIT Press, Cambridge MA, 1984.

Digital Library

[31]

P. Thomas. The Petri Net: A Modeling Tool for the Coordination of Asynchronous processes. Master's thesis, University of Tennessee. 1976.

Cited By

Benavides Navarro LDouence RSüdholt M(2008)Debugging and Testing Middleware with Aspect-Based Control-Flow and Causal PatternsProceedings of the ACM/IFIP/USENIX 9th International Middleware Conference10.1007/978-3-540-89856-6_10(183-202)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1007/978-3-540-89856-6_10
Baldy PDicky HMedina RMorvan MVilarem J(2005)Efficient reconstruction of the causal relationship in distributed systemsParallel and Distributed Computing Theory and Practice10.1007/3-540-58078-6_10(101-113)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-58078-6_10
Hrischuk CWoodside C(2002)Logical Clock Requirements for Reverse Engineering Scenarios from a Distributed SystemIEEE Transactions on Software Engineering10.1109/TSE.2002.99541628:4(321-339)Online publication date: 1-Apr-2002
https://dl.acm.org/doi/10.1109/TSE.2002.995416
Show More Cited By

Recommendations

Modeling concurrency in parallel debugging
PPOPP '90: Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming

We propose a debugging language, Data Path Expressions (DPEs), for modeling the behavior of parallel programs. The debugging paradigm is for the programmer to describe the expected program behavior and for the debugger to compare the actual program ...
Concurrency debugging with MaxSMT
AAAI'19/IAAI'19/EAAI'19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence

Current Maximum Satisfability (MaxSAT) algorithms based on successive calls to a powerful Satisfability (SAT) solver are now able to solve real-world instances in many application domains. Moreover, replacing the SAT solver with a Satisfability Modulo ...
Debugging non-deadlock concurrency bugs
ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and Analysis

Concurrency bugs are difficult to debug because of nondeterministic behaviors of concurrent programs. Existing fault-localization techniques for non-deadlock concurrency bugs do not provide the comprehensive information to identify and understand the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 25, Issue 3

Mar. 1990

216 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/99164

Editor:
David Padua
Univ. of Illinois at Urbana/Champaign, Urbana

Issue’s Table of Contents

PPOPP '90: Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming
February 1990
206 pages
ISBN:0897913507
DOI:10.1145/99163
Chairman:
David Padua
Univ. of Illinois at Urbana/Champaign, Urbana

Copyright © 1990 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1990

Published in SIGPLAN Volume 25, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
554
Total Downloads

Downloads (Last 12 months)109
Downloads (Last 6 weeks)25

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Benavides Navarro LDouence RSüdholt M(2008)Debugging and Testing Middleware with Aspect-Based Control-Flow and Causal PatternsProceedings of the ACM/IFIP/USENIX 9th International Middleware Conference10.1007/978-3-540-89856-6_10(183-202)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1007/978-3-540-89856-6_10
Baldy PDicky HMedina RMorvan MVilarem J(2005)Efficient reconstruction of the causal relationship in distributed systemsParallel and Distributed Computing Theory and Practice10.1007/3-540-58078-6_10(101-113)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-58078-6_10
Hrischuk CWoodside C(2002)Logical Clock Requirements for Reverse Engineering Scenarios from a Distributed SystemIEEE Transactions on Software Engineering10.1109/TSE.2002.99541628:4(321-339)Online publication date: 1-Apr-2002
https://dl.acm.org/doi/10.1109/TSE.2002.995416
Huang YRavishankar C(1998)Constructive Protocol Specification Using CiceroIEEE Transactions on Software Engineering10.1109/32.67718324:4(252-267)Online publication date: 1-Apr-1998
https://dl.acm.org/doi/10.1109/32.677183
Carlisle W(1995)Type checking concurrent I/OACM Transactions on Programming Languages and Systems10.1145/203095.20309717:3(448-460)Online publication date: 1-May-1995
https://dl.acm.org/doi/10.1145/203095.203097
Wirtz G(1995)Modularization, re-use and testing for parallel message-passing programsProceedings of the Twenty-Eighth Hawaii International Conference on System Sciences10.1109/HICSS.1995.375448(299-308)Online publication date: 1995
https://doi.org/10.1109/HICSS.1995.375448
Schwarz RMattern F(1994)Detecting causal relationships in distributed computationsDistributed Computing10.1007/BF022778597:3(149-174)Online publication date: 1-Mar-1994
https://dl.acm.org/doi/10.1007/BF02277859
Ponamgi MHseush WKaiser G(1991)Debugging Multithreaded Programs with MPDIEEE Software10.1109/52.889428:3(37-43)Online publication date: 1-May-1991
https://dl.acm.org/doi/10.1109/52.88942
O'toole ENallur VClarke S(2017)Decentralised Detection of Emergence in Complex Adaptive SystemsACM Transactions on Autonomous and Adaptive Systems10.1145/301959712:1(1-31)Online publication date: 6-Apr-2017
https://dl.acm.org/doi/10.1145/3019597
Lin CNagarajan VGupta RRajaram B(2012)Efficient sequential consistency via conflict orderingACM SIGPLAN Notices10.1145/2248487.215100647:4(273-286)Online publication date: 3-Mar-2012
https://dl.acm.org/doi/10.1145/2248487.2151006
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Issue’s Table of Contents