About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1992
Conference paper
Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible!
Abstract
In a timestamping system processors repeatedly choose labels in such a way that the order of the labels assigned reflects the real-time order in which they were requested. Concurrent timestamping systems permit requests by multiple processors to be issued concurrently; in bounded timestamping systems the sizes of the labels and the amount of auxiliary storage are bounded. Letting n denote the number of processors, we construct a simple bounded concurrent timestamping system requiring O(n) steps (accesses to shared memory) to read the current labels and determine the order among them, and O(n) steps to generate a label. In addition, we introduce the Traceable Use abstraction, which, roughly speaking, permits a processor to know and to control which of its own values are currently in use in the system.