skip to main content
10.1145/1500774.1500850acmotherconferencesArticle/Chapter ViewAbstractPublication PagesafipsConference Proceedingsconference-collections
research-article
Free access

Fair timestamp allocation in distributed systems

Published: 07 June 1982 Publication History

Abstract

Many researchers have addressed the problem of uniquely identifying updates in a distributed database system in the literature. Primitive identification schemes that generate globally unique update IDs have also been suggested. These IDs are usually used as priority among updates as well. When used as such, these schemes do not distribute priority evenly across the nodes. This paper presents a numbering scheme that generates unique update IDs and, if used as a priority scheme, is fair.

References

[1]
Bernstein, P. A., J. B. Rothnie, N. Goodman, and C. A. Papadimitriou. "The Concurrency Control Mechanism of SDD--1: A System for Distributed Data Bases (The Fully Redundant Case)." IEEE Transactions on Software Engineering, SE--4, (1978).
[2]
Date, C. J. "An Introduction to Database Systems." Addison-Wesley, Reading, Massachusetts, 1977.
[3]
Everest, G. C. "Concurrent Update Control and Database Integrity." In J. W. Klimbie and K. L. Koffeman (eds.), Database Management. Amsterdam: North-Holland, 1974, pp. 241--268.
[4]
Eswaran, K. P.; J. N. Gray, R. A. Lorie, and I. L. Traiger. "The Notions of Consistency and Predicate Locks in a Database System." Communications of the ACM, 19 (1976).
[5]
Lamport, L. "Time, Clocks, and the Ordering of Events in a Distributed System." Communications of the ACM, 21 (1978).
[6]
Lelann, G. "Algorithms for Distributed Data-Sharing Systems Which Use Tickets." Proc. Third Berkeley Workshop on Distributed Data Base and Computer Networks. University of California, Berkeley, CA, August 1978.
[7]
Rahimi, S. K., and W. R. Franta, "A Posted Update Approach to Concurrency Control in Distributed Data Base Systems." Proc. 1st Intl. Conf. on Distributed Computing Systems, IEEE, Oct. 1979.
[8]
Reed, D. P. "Naming and Synchronization in a Decentralized Computer System." Ph.D. thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, September 1978.
[9]
Rosenkrantz, D. J., R. E. Stearns, and P. M. Lewis, II. "System Level Concurrency Control for Distributed Database Systems." ACM Transactions on Database Systems, 3 (1978).
[10]
M. Stonebraker. "Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES." 3rd Berkeley Workshop on Distributed Data Management, 1978.
[11]
Thomas, R. H. "A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases." ACM Transactions on Database Systems, 4 (1979).
[12]
Traiger, I. L., J. N. Gray, C. A. Galtieri, and B. G. Lindsay. "Transactions and Consistency in Distributed Data Base Systems." IBM Report RJ2555 (33155), May 1979.

Cited By

View all
  • (2023)Distributed Logical Timestamp Allocation for DBMS Concurrency Control on Many-core MachinesProceedings of the 32nd International Symposium on High-Performance Parallel and Distributed Computing10.1145/3588195.3595942(313-314)Online publication date: 7-Aug-2023
  • (2018)Logical Clocks Are Not FairProceedings of the 2018 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed systems10.1145/3231104.3231109(21-27)Online publication date: 23-Jul-2018

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
AFIPS '82: Proceedings of the June 7-10, 1982, national computer conference
June 1982
857 pages
ISBN:088283035X
DOI:10.1145/1500774
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]

Sponsors

  • AFIPS: American Federation of Information Processing Societies

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 1982

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1,828
  • Downloads (Last 6 weeks)12
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Distributed Logical Timestamp Allocation for DBMS Concurrency Control on Many-core MachinesProceedings of the 32nd International Symposium on High-Performance Parallel and Distributed Computing10.1145/3588195.3595942(313-314)Online publication date: 7-Aug-2023
  • (2018)Logical Clocks Are Not FairProceedings of the 2018 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed systems10.1145/3231104.3231109(21-27)Online publication date: 23-Jul-2018

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media