Article

Free access

An approach to performance analysis of timestamp-driven synchronization mechanisms

Authors:

David Jefferson,

Andrew WitkowskiAuthors Info & Claims

PODC '84: Proceedings of the third annual ACM symposium on Principles of distributed computing

Pages 243 - 253

https://doi.org/10.1145/800222.806751

Published: 27 August 1984 Publication History

PDF eReader

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]

P.A. Bernstein and N. Goodman. "Concurrency Control in Distributed Database Systems." Computing Surveys 13, 2 (June 1981).]]

Digital Library

Google Scholar

[2]

Chang, Youan. Personal communication. Forthcoming in a paper]]

Google Scholar

[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.]]

Google Scholar

[4]

Jefferson, D.R. and Sowizral, H. Fast Concurrent Simulation Using Time Warp Mechanism, Part1: Local Control. Rand Corporation, Santa Monica, Cal., 1982.]]

Google Scholar

[5]

Parzen, E., Stochastic Processes. Holden-Day, 1961.]]

Digital Library

Google Scholar

[6]

Reed, D.P. "Implementing Atomic Actions on Decentralized Data." ACM Transactions on Computer Systems 1 (February 1983).]]

Digital Library

Google Scholar

[7]

Ross, S.M., Introduction to Probability Models. Academic Press, Inc., 1972.]]

Digital Library

Google Scholar

[8]

Silberschatz, A. A Multiversion Concurrency Control Scheme With No Rollbacks. Proc. ACM SIGACT-SIGOPS Symp. Principles of Distributed Computing, Ottawa, Canada, August, 1982, pp. 216-223.]]

Digital Library

Google Scholar

Cited By

View all

Manita ASimonot F(2005)Clustering in stochastic asynchronous algorithms for distributed simulationsProceedings of the Third international conference on StochasticAlgorithms: foundations and applications10.1007/11571155_3(26-37)Online publication date: 20-Oct-2005
https://dl.acm.org/doi/10.1007/11571155_3
Akyildiz IChen LDas SFujimoto RSerfozo R(1993)The Effect of Memory Capacity on Time Warp PerformanceJournal of Parallel and Distributed Computing10.1006/jpdc.1993.107418:4(411-422)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1006/jpdc.1993.1074
Akyildiz IChen LDas SFujimoto RSerfozo R(1992)Performance analysis of “Time Warp” with limited memoryACM SIGMETRICS Performance Evaluation Review10.1145/149439.13310920:1(213-224)Online publication date: 1-Jun-1992
https://dl.acm.org/doi/10.1145/149439.133109
Show More Cited By

Index Terms

An approach to performance analysis of timestamp-driven synchronization mechanisms

Recommendations

Performance evaluation of timestamp-driven databases
A TimeStamp Based Multi-version STM Algorithm
ICDCN 2014: Proceedings of the 15th International Conference on Distributed Computing and Networking - Volume 8314

Software Transactional Memory Systems STM are a promising alternative for concurrency control in shared memory systems. Multiversion STM systems maintain multiple versions for each t-object. The advantage of storing multiple versions is that it ...
Commit phase in timestamp-based stm
SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures

Timestamp-based Software Transactional Memory (STM)validation techniques use a global shared counter and timestamping of objects being written to reason about sequencing of transactions and their linearization points, while reducing the number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '84: Proceedings of the third annual ACM symposium on Principles of distributed computing

August 1984

301 pages

ISBN:0897911431

DOI:10.1145/800222

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: 27 August 1984

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
344
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)10

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Manita ASimonot F(2005)Clustering in stochastic asynchronous algorithms for distributed simulationsProceedings of the Third international conference on StochasticAlgorithms: foundations and applications10.1007/11571155_3(26-37)Online publication date: 20-Oct-2005
https://dl.acm.org/doi/10.1007/11571155_3
Akyildiz IChen LDas SFujimoto RSerfozo R(1993)The Effect of Memory Capacity on Time Warp PerformanceJournal of Parallel and Distributed Computing10.1006/jpdc.1993.107418:4(411-422)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1006/jpdc.1993.1074
Akyildiz IChen LDas SFujimoto RSerfozo R(1992)Performance analysis of “Time Warp” with limited memoryACM SIGMETRICS Performance Evaluation Review10.1145/149439.13310920:1(213-224)Online publication date: 1-Jun-1992
https://dl.acm.org/doi/10.1145/149439.133109
Akyildiz IChen LDas SFujimoto RSerfozo RMolloy M(1992)Performance analysis of “Time Warp” with limited memoryProceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems10.1145/133057.133109(213-224)Online publication date: 1-Jun-1992
https://dl.acm.org/doi/10.1145/133057.133109
Gupta AAkyildiz IFujimoto R(1991)Performance analysis of Time Warp with homogeneous processors and exponential task timesACM SIGMETRICS Performance Evaluation Review10.1145/107972.10798319:1(101-110)Online publication date: 2-Apr-1991
https://dl.acm.org/doi/10.1145/107972.107983
Gupta AAkyildiz IFujimoto RKeller T(1991)Performance analysis of Time Warp with homogeneous processors and exponential task timesProceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems10.1145/107971.107983(101-110)Online publication date: 2-Apr-1991
https://dl.acm.org/doi/10.1145/107971.107983
Gupta AAkyildiz IFujimoto R(1991)Performance Analysis of Time Warp with Multiple Homogeneous ProcessorsIEEE Transactions on Software Engineering10.1109/32.9919017:10(1013-1027)Online publication date: 1-Oct-1991
https://dl.acm.org/doi/10.1109/32.99190
Jefferson DDwork C(1990)Virtual time II: storage management in conservative and optimistic systemsProceedings of the ninth annual ACM symposium on Principles of distributed computing10.1145/93385.93403(75-89)Online publication date: 1-Aug-1990
https://dl.acm.org/doi/10.1145/93385.93403
Jefferson D(1985)Virtual timeACM Transactions on Programming Languages and Systems10.1145/3916.39887:3(404-425)Online publication date: 1-Jul-1985
https://dl.acm.org/doi/10.1145/3916.3988

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Performance evaluation of timestamp-driven databases

A TimeStamp Based Multi-version STM Algorithm

Commit phase in timestamp-based stm