An approach to performance analysis of timestamp-driven synchronization mechanisms

ABSTRACT

In this paper we introduce a new analytical approach to modeling the performance of systems synchronized by timestamp mechanisms, including database systems. We define the virtual time - real time (T-V) plane, and an important kind of stochastic process that we call linear Poisson processes. We show how to calculate the rate of preemption (corresponding to the rate of abortion or rollback in concurrency control mechanisms) and the waiting time until last preemption (corresponding to commit time) for linear Poisson processes. Finally, we apply this theory, analyzing one example system synchronized by the Time Warp mechanism.

REFERENCES

• 1: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 2: Chang, Youan. Personal communication. Forthcoming in a paper
• 3: Jefferson, D.R. and Motro, A. The Time Warp Concurrency Control Mechanism For Distributed Databases. Department of Computer Science, University of Southern California, Los Angeles, California, 90089-0782, June, 1983.
• 4: Jefferson, D.R. and Sowizral, H. Fast Concurrent Simulation Using Time Warp Mechanism, Part1: Local Control. Rand Corporation, Santa Monica, Cal., 1982.
• 5: Emanuel Parzen, Stochastic processes, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 6: David P. Reed, Implementing atomic actions on decentralized data, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.3-23, Feb. 1983 [doi>10.1145/357353.357355]
• 7: Ross, S.M., Introduction to Probability Models. Academic Press, Inc., 1972.
• 8: Abraham Silberschatz, A multi-version concurrency scheme with no rollbacks, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.216-223, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806700]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Algorithms, Management, Performance, Theory