More Web Proxy on the site http://driver.im/

Article

Free access

Bounded concurrrent time-stamp systems are constructible

Authors:

N. ShavitAuthors Info & Claims

STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

Pages 454 - 466

https://doi.org/10.1145/73007.73051

Published: 01 February 1989 Publication History

Abstract

Concurrent time stamping is at the heart of solutions to some of the most fundamental problems in distributed computing. Based on concurrent-time-stamp-systems, elegant and simple solutions to core problems such as ƒcƒs-mutual-exclusion, construction of a multi-reader-multi-writer atomic register, probabilistic consensus,… were developed. Unfortunately, the only known implementation of a concurrent time stamp system has been theoretically unsatisfying, since it requires unbounded size time-stamps, in other words, unbounded memory. Not knowing if bounded concurrent-time-stamp-systems are at all constructible, researchers were led to constructing complicated problem-specific solutions to replace the simple unbounded ones. In this work, for the first time, a bounded implementation of a concurrent-time-stamp-system is presented. It provides a modular unbounded-to-bounded transformation of the simple unbounded solutions to problems such as above. It allows solutions to two formerly open problems, the bounded-probabilistic-consensus problem of Abrahamson [A88] and the ƒiƒo-@@@@-exclusion problem of [FLBB85], and a more efficient construction of mrmw atomic registers.

References

[1]

Y, Afek, D. Dolev, M. Merrltt, and N. Shavit, "A Bounded fifo solution to the /-exclusion problem,'* in preparation.

[2]

K. Abrahamson, "On Achieving Consensus Using a Shared Memory," Proc. 7th A GM Syrup. on Principles of Distributed GomputintT, 1988, pp. 291-302.

Digital Library

[3]

J.H. Anderson, and M. (3. Gouda, "The Virtue of Patience: Concurrent Programrning With and Without Waiting," unpublished manuscript, Dept. of Computer Science, Austin, Texas, Jan. 1988.

Digital Library

[4]

H. Attiya, D. Dolev, and N. Shavit, "A Bounded Probabilistic Shared-Memory Consensus Algorithm," unpublished manuscript.

[5]

S. Ben-David, "The Global Time Assumption and Semantics for Concurrent Systems," Proc. 7th A CM Syrup. on Principles of Distributed Computing, 1988, pp. 223-231.

Digital Library

[6]

B. Bloom, "Constructing two-writer atomic registers," Proc. 6th A CM Syrap. on Principles oJ Distributed Computing, 1987, pp. 249- 259.

Digital Library

[7]

J.E. Burns, and G. L. Peterson, "Constructing Multi-Reader Atomic Values from Non-Atomic Values," Proc. 6tk A CM Syrup. on Principles of Distributed Computing, 1987, pp. 222-231.

Digital Library

[8]

B. Chor, A. Israeli, and M. Li, "On Processor Coordination Using Asynchronous Hardware", Proc. 6th A CM Syrup. on Principles of Distributed Computing, 1987, pp. 86-97.

Digital Library

[9]

E.W. Dijkstra, "Solution of a Problem in Concm-rent Programming Control," CA CM 8, 9, 1965, p. 569.

Digital Library

[10]

D. Dolev, E. Gafni, and N. Shavit, "Toward a Non-Atomic Era: L-Exclusion as a Test Case," Proc. ~Oth Annual A CM Syrup. on the Theory of Computing, 1988.

Digital Library

[11]

M. $. Fischer, N. A. Lynch, J. E. Burns, and A. Borodin, "Resource Allocation with Immunity to Limited Process Failure," Proc. 20th IEEE Syrup. on Foundations of Computer Science, 1979, pp. 234-254.

[12]

M.J. Fischer, N. A. Lynch, J. E. Burns, and A. Borodin, "Distributed fifo Allocation of Identical Resources Using Small Shared Space," MIT/LCS/TM-290, 1985.

[13]

M.P. Herlihy, "WaitFree Implementations of Concurrent Objects," Proc. 7th A CM Syrup. on Principles of Distributed Computing, 1988, pp. 276- 290.

Digital Library

[14]

A. Israeli and M. Li, "Bounded Time Stamps," Proc. 28th Annual IEEE Syrup. on Foundations of Computer Science, 1987, pp. 371-382.

[15]

H.P. Katseff, "A New Solution to the Critical Section Problem," Proc. l Oth Annual ACM Symposium on the Theory of Computing, 1978, pp. 86-88.

Digital Library

[16]

L. Larnport, "A new Solution of Dijkstra's Concurrent programming problem," CA CM 17, 8 1974, pp. 453-455.

Digital Library

[17]

L. Lamport, "On Interprocess Communication. Part I: Basic Formalism," Distributed Computing i, ~ 1986, 77-85.

[18]

L. Lamport, "On Interprocess Communication. Part II: Algorithms," Distributed Computing 1, 2 1986, pp. 86-101.

[19]

L. Larnport, "The Mutual Exclusion Problem. Part {: A Theory of Interprocess Communication,'' J. ACM 33, 2 1986, pp. 313-326.

Digital Library

[20]

L. Lamport, "The Mutual Exclusion Problem. Part II: Statement and Solutions," J. ACM 33, 2 1986, pp. 327-348.

Digital Library

[21]

M. Li, and P. Vitanyi, "Uniform Construction for Wait-Free Variables," unpublished manuscript, 1988.

[22]

E.A. Lycldama and V. Hadzilacos, "A Fair Mutual Exclusion Algorithm With Small Cornmunication Variables," submitted for publication, 1988.

[23]

R. Newmaxt-XNolfe, "A Protocol for Waitfree Atomic, Multi Reader Shared Variables," Proc. 6tk A CM Syrup. o~ Principles of Distributed Computing, 1987, pp. 232-248.

Digital Library

[24]

(3. L. Peterson, "Myths about the Mutual- Exclusion Problem," IPL 1~, 3 1981, pp. 115~ 116.

[25]

G.L. Peterson, "Concurrent Reading While Writing," A CM TOPLAS 5, 1 1983, pp. 46- 55.

Digital Library

[26]

G.L. Peterson, and J. E. Bums, "Concurrent Reading While Writing Ii: The Multi- Writer Case," Proc. ~Sth Ann~el iEEE Syrup. on Foundations of Computer Science, 1987, pp. 383-392.

[27]

(3. L. Peterson, personal communication.

[28]

M. Raynal, Algorithms for Mutual Exclusion, North Oxford Academic, 1986.

Digital Library

[29]

R. Schaffer, "On the Correctness of Atomic Multi-Writer Registers," MIT/LCS/TM-364, June 1988.

[30]

A. K. Singh, J. H. Anderson and M. (3. Gouda, "The Elusive Atomic Register Revisited,'' Proc. 6th A CM Syrup. on Principles of Distributed Computing, 1987, pp 206-221.

Digital Library

[31]

P. Vitanyi, and B. Awerbuch, "Atomic Shared Register Access by Asynchronous Hardware," Proc. 27th Annual IEEE Syrup. on Foundations of Computer Science, 1986, pp. 233-243.

Cited By

Rajagopalan KSrinivasan VThomo A(2012)Learning the news in social networksProceedings of the 7th international conference on Foundations of Information and Knowledge Systems10.1007/978-3-642-28472-4_17(298-311)Online publication date: 5-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28472-4_17
Danek RRicha AGuerraoui R(2010)The k-bakeryProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835707(36-44)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835707
Gontmakher AMendelson ASchuster AShklover G(2006)Speculative Synchronization and Thread Management for Fine Granularity ThreadsThe Twelfth International Symposium on High-Performance Computer Architecture, 2006.10.1109/HPCA.2006.1598136(283-292)Online publication date: 2006
https://doi.org/10.1109/HPCA.2006.1598136
Show More Cited By

Index Terms

Recommendations

Bounded concurrent timestamp systems using vector clocks

Shared registers are basic objects used as communication mediums in asynchronous concurrent computation. A concurrent timestamp system is a higher typed communication object, and has been shown to be a powerful tool to solve many concurrency control ...
Bounded Concurrent Time-Stamping

We introduce concurrent time-stamping, a paradigm that allows processes to temporally order concurrent events in an asynchronous shared-memory system. Concurrent time-stamp systems are powerful tools for concurrency control, serving as the basis for ...
Modeling and Analysis of a Time-Stamp History Based Certification Protocol for Concurrency Control

An examination is made of a technique to derive the time-stamp or interval of time-stamps dynamically by using limited time-stamp history information to re-order transaction at commit time and to derive a back-shifted time-stamp for certification to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

February 1989

600 pages

ISBN:0897913078

DOI:10.1145/73007

Editor:
D. S. Johnson

Copyright © 1989 ACM.

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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC89

Sponsor:

SIGACT

STOC89: 21st Annual ACM Symposium on the Theory of Computing

May 14 - 17, 1989

Washington, Seattle, USA

Acceptance Rates

STOC '89 Paper Acceptance Rate 56 of 196 submissions, 29%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
476
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)2

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rajagopalan KSrinivasan VThomo A(2012)Learning the news in social networksProceedings of the 7th international conference on Foundations of Information and Knowledge Systems10.1007/978-3-642-28472-4_17(298-311)Online publication date: 5-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28472-4_17
Danek RRicha AGuerraoui R(2010)The k-bakeryProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835707(36-44)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835707
Gontmakher AMendelson ASchuster AShklover G(2006)Speculative Synchronization and Thread Management for Fine Granularity ThreadsThe Twelfth International Symposium on High-Performance Computer Architecture, 2006.10.1109/HPCA.2006.1598136(283-292)Online publication date: 2006
https://doi.org/10.1109/HPCA.2006.1598136
Li MVitanyi P(2005)How to share concurrent asynchronous wait-free variablesAutomata, Languages and Programming10.1007/BFb0035779(488-505)Online publication date: 29-Nov-2005
https://doi.org/10.1007/BFb0035779
Mukund MKumar KSohoni M(2003)Bounded time-stamping in message-passing systemsTheoretical Computer Science10.1016/S0304-3975(01)00329-2290:1(221-239)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1016/S0304-3975%2801%2900329-2
Malkhi DReiter MLeighton FShor P(1997)Byzantine quorum systemsProceedings of the twenty-ninth annual ACM symposium on Theory of computing10.1145/258533.258650(569-578)Online publication date: 4-May-1997
https://dl.acm.org/doi/10.1145/258533.258650
Aspnes JHurwood WBurns JMoses Y(1996)Spreading rumors rapidly despite an adversaryProceedings of the fifteenth annual ACM symposium on Principles of distributed computing10.1145/248052.248077(143-151)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1145/248052.248077
Aspnes JWaarts OMiller G(1996)Modular competitiveness for distributed algorithmsProceedings of the twenty-eighth annual ACM symposium on Theory of Computing10.1145/237814.237869(237-246)Online publication date: 1-Jul-1996
https://dl.acm.org/doi/10.1145/237814.237869
Manhoi Choy (1996)Robust distributed mutual exclusionProceedings of 16th International Conference on Distributed Computing Systems10.1109/ICDCS.1996.508029(760-767)Online publication date: 1996
https://doi.org/10.1109/ICDCS.1996.508029
Neiger GAnderson J(1995)Failure detectors and the wait-free hierarchy (extended abstract)Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing10.1145/224964.224976(100-109)Online publication date: 20-Aug-1995
https://dl.acm.org/doi/10.1145/224964.224976
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten