Event-based detection of concurrency

ABSTRACT

Understanding the behavior of a system is crucial in being able to modify, maintain, and improve the system. A particularly difficult aspect of some system behaviors is concurrency. While there are many techniques to specify intended concurrent behavior, there are few, if any, techniques to capture and model actual concurrent behavior. This paper presents a technique to discover patterns of concurrent behavior from traces of system events. The technique is based on a probabilistic analysis of the event traces. Using metrics for the number, frequency, and regularity of event occurrences, a determination is made of the likely concurrent behavior being manifested by the system. The technique is useful in a wide variety of software engineering tasks, including architecture discovery, reengineering, user interaction modeling, and software process improvement.

REFERENCES

• 1: R. Agrawal, D. Gunopulos, and F. Leymann. Mining Process Models from Workflow Logs. Technical Report (draft technical report), IBM, September 1997.
• 2: George S. Avrunin , Ugo A. Buy , James C. Corbett , Laura K. Dillon , Jack C. Wileden, Automated Analysis of Concurrent Systems with the Constrained Expression Toolset, IEEE Transactions on Software Engineering, v.17 n.11, p.1204-1222, November 1991 [doi>10.1109/32.106975]
• 3: Peter Bates, Debugging heterogeneous distributed systems using event-based models of behavior, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.11-22, May 05-06, 1988, Madison, Wisconsin, United States
• 4: Jonathan E. Cook , Alexander L. Wolf, Automating process discovery through event-data analysis, Proceedings of the 17th international conference on Software engineering, p.73-82, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225021]
• 5: Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998 [doi>10.1145/287000.287001]
• 6: Janice Cuny , George Forman , Alfred Hough , Joydip Kundu , Calvin Lin , Lawrence Snyder , David Stemple, The Ariadne debugger: scalable application of event-based abstraction, Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, p.85-95, May 17-18, 1993, San Diego, California, United States
• 7: J.L. Devore. Probability and Statistics for Engineering and the Sciences. Brooks/Cole, Pacific Grove, California, 3rd edition, 1991.
• 8: Michel Diaz , Guy Juanole , Jean-Pierre Courtiat, Observer-A Concept for Formal On-Line Validation of Distributed Systems, IEEE Transactions on Software Engineering, v.20 n.12, p.900-913, December 1994 [doi>10.1109/32.368136]
• 9: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 10: Lester J. Holtzblatt , Richard L. Piazza , Howard B. Reubenstein , Susan N. Roberts , David R. Harris, Design Recovery for Distributed Systems, IEEE Transactions on Software Engineering, v.23 n.7, p.461-472, July 1997 [doi>10.1109/32.605763]
• 11: E. Koutsofios and S.C. North. Draxving Graphs vJith Dot. AT&T Bell Laboratories, October 1993.
• 12: R.J. LeBlanc and A.D. Robbins. Event-Driven Monitoring of Distributed Programs. In Proceedings of the Fifth Zntemational Conference on Distributed Computing Systems, pages 515522. IEEE Computer Society, May lSS5.
• 13: James L. Peterson, Petri Nets, ACM Computing Surveys (CSUR), v.9 n.3, p.223-252, Sept. 1977 [doi>10.1145/356698.356702]
• 14: S. Venkatesan , Brhama Dathan, Testing and Debugging Distributed Programs Using Global Predicates, IEEE Transactions on Software Engineering, v.21 n.2, p.163-177, February 1995 [doi>10.1109/32.345831]
• 15: A.L. Wolf and D.S. Rosenblum. A Study in Softxvare Process Data Capture and Analysis. In Proceedings of the Second International Conference on the Software Process, pages 115-124. IEEE Computer Society, February 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory