Bounded concurrent timestamp systems using vector clocks

DOI10.1145/505241.505246MaRDI QIDQ3196636zbMATH OpenOpenAlexFDO

Authors S. Haldar, Paul M. B. Vitányi

Publication date 30 October 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0108002

zbMATH Keywords

concurrent reading while writinglabelingnonatomic operation executionread and writescanshared variable-safetimestamp systemtraceabilityvector clockwait-freedom

Mathematics Subject Classification ID

Theory of operating systems (68N25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: 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 problems. It has turned out to be possible to construct such higher typed objects from primitive lower typed ones. The next step is to find efficient constructions. We propose a very efficient wait-free construction of bounded concurrent timestamp systems from 1-writer multireader registers. This finalizes, corrects, and extends, a preliminary bounded multiwriter construction proposed by the second author in 1986. That work partially initiated the current interest in wait-free concurrent objects, and introduced a notion of discrete vector clocks in distributed algorithms.

Recommendations

• Bounded Concurrent Time-Stamping
• An efficient implementation of vector clocks
• Simple and efficient bounded concurrent timestamping and the traceable use abstraction
• scientific article; zbMATH DE number 1979529
• The Space Complexity of Unbounded Timestamps

Cited in

(17)

• Ubiquity of scalar timing with a Poisson clock
• An efficient implementation of vector clocks
• Byzantine disk paxos: optimal resilience with Byzantine shared memory
• Verifying a simplification of mutual exclusion by Lycklama-Hadzilacos
• On the interconnection of message passing systems
• Simple and efficient bounded concurrent timestamping and the traceable use abstraction
• The space complexity of unbounded timestamps
• Bounded Concurrent Time-Stamping
• An algorithm for exact bounds on the time separation of events in concurrent systems
• scientific article; zbMATH DE number 1979529 (Why is no real title available?)
• scientific article; zbMATH DE number 1863250 (Why is no real title available?)
• Randomized two-process wait-free test-and-set
• Efficient dependency tracking for relevant events in shared-memory systems
• Bounded Version Vectors
• Efficient Bounded Timestamping from Standard Synchronization Primitives
• Efficient bounded timestamping from standard synchronization primitives
• Wait-free regular storage from Byzantine components

This page was built for publication: Bounded concurrent timestamp systems using vector clocks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196636)