On-the-fly calculation and verification of consistent steering transactions

ABSTRACT

Interactive Steering can be a valuable tool for understanding and controlling a distributed computation in real-time. With Interactive Steering, the user may change the state of a computation by adjusting application parameters on-the-fly. In our system, we model both the program's execution and steering actions in terms of transactions. We define a steering transaction as consistent if its vector time is not concurrent with the vector time of any program transaction. That is, consistent steering transactions occur "between" program transactions, at a point that represents a consistent cut. In this paper, we present an algorithm for verifying the consistency of steering transactions. The algorithm analyzes a record of the program transactions and compares it against the steering transaction; if the time at which the steering transaction was applied is inconsistent, the algorithm generates a vector representing the earliest consistent time at which the steering transaction could have been applied.

REFERENCES

• 1: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 2: Dijkstra and B.P. Scholten, "Termination Detections for Diffusing Computations," Information Processing Letters, 1980, 11(1): 1-4.
• 3: J. Fowler and W. Zwaenepoel, "Casual Distributed Breakpoints," in Proceedings, 10th International Conference on Distributed Computing Systems, Paris, France, May 1990, pp. 134-141.
• 4: C.J. Fidge, "Timestamps in Message-Passing Systems that Preserve the Partial Ordering", Australian Computer Science Communications, February 1988, pp. 56-66.
• 5: Weiming Gu , G. Eisenhauer , E. Kraemer , K. Schwan , J. Stasko , J. Vetter , N. Mallavarupu, Falcon: on-line monitoring and steering of large-scale parallel programs, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.422, February 06-09, 1995
• 6: Delbert Hart , Eileen Kraemer, Interactive Visual Exploration of Distributed Computations, Proceedings of the 11th International Symposium on Parallel Processing, p.121-127, April 01-05, 1997
• 7: Delbert Hart , Eileen Kraemer, An agent-based perspective on distributed monitoring and steering, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.151, August 03-04, 1998, Welches, Oregon, United States [doi>10.1145/281035.281053]
• 8: Eileen Kraemer , Delbert Hart , Gruia-Catalin Roman, Balancing Consistency and Lag in Transaction-Based Computational Steering, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 7, p.137, January 06-09, 1998 [doi>10.1109/HICSS.1998.649207]
• 9: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 10: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 11: F. Mattern, "Virtual Time and Global States of Distributed Systems," Parallel and Distributed Algorithms, North-Holland, 1989, pp. 215-226.
• 12: Friedemann Mattern, Efficient algorithms for distributed snapshots and global virtual time approximation, Journal of Parallel and Distributed Computing, v.18 n.4, p.423-434, Aug. 1993 [doi>10.1006/jpdc.1993.1075]
• 13: Robert H. B. Netzer , Jian Xu, Necessary and Sufficient Conditions for Consistent Global Snapshots, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.165-169, February 1995 [doi>10.1109/71.342127]
• 14: P. M. Papadopoulos , J. A. Kohl , B. D. Semeraro, Philip M. Papadopoulos, James Arthur Kohl, B. David Semeraro, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 7, p.127, January 06-09, 1998 [doi>10.1109/HICSS.1998.649206]
• 15: Reinhard Schwarz , Friedemann Mattern, Detecting causal relationships in distributed computations: in search of the holy grail, Distributed Computing, v.7 n.3, p.149-174, March 1994 [doi>10.1007/BF02277859]
• 16: Jeffrey S. Vetter , Karsten Schwan, High Performance Computational Steering of Physical Simulations, Proceedings of the 11th International Symposium on Parallel Processing, p.128, April 01-05, 1997
• 17: J. Vetter and K. Schwan. "Progress: A Toolk it for Interactive Program Steering," Proceedings of the 1995 International Conference on Parallel Processing, Urbana, IL, Aug 1995, pp. 139-142.
• 18: H. Vuppula, E. Kraemer, and D. Hart, "Algorithms for Collection of Global Snapshots: An Empirical Evaluation," Proceedings in, ICSA Conference on Parallel and Distributed Computing Systems, August 2000, pp. 197-204.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

General Terms:
Algorithms, Design, Performance

Keywords:
consistent cut, consistent steering, consistent transaction, happened before, program event, program transaction, steering event, steering transaction